Submission #1365423


Source Code Expand

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

class Ruiwa():
    def __init__(self, a):
        self.H = h = len(a)
        self.W = w = len(a[0])
        self.R = r = a
        for i in range(h):
            for j in range(1,w):
                r[i][j] += r[i][j-1]

        for i in range(1,h):
            for j in range(w):
                r[i][j] += r[i-1][j]

    def search(self, x1, y1, x2, y2):
        if x1 > x2 or y1 > y2:
            return 0

        r = self.R
        rr = r[y2][x2]
        if x1 > 0 and y1 > 0:
            return rr - r[y1-1][x2] - r[y2][x1-1] + r[y1-1][x1-1]
        if x1 > 0:
            rr -= r[y2][x1-1]
        if y1 > 0:
            rr -= r[y1-1][x2]

        return rr

def main():
    h,w = LI()
    a = []
    for i in range(h):
        t = LI()
        a.append([t[j] if (i+j)%2 == 0 else -t[j] for j in range(w)])

    rui = Ruiwa(a)
    r = 0
    for i in range(h):
        for j in range(w):
            for ii in range(i,h):
                for jj in range(j,w):
                    if rui.search(j,i,jj,ii) == 0:
                        t = (ii-i+1) * (jj-j+1)
                        if r < t:
                            r = t

    return r


print(main())

Submission Info

Submission Time
Task B - チョコレート
User iehn
Language PyPy3 (2.4.0)
Score 100
Code Size 1746 Byte
Status AC
Exec Time 1262 ms
Memory 72812 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 5
AC × 25
Set Name Test Cases
Sample subtask0_sample-01.txt, subtask0_sample-02.txt, subtask0_sample-03.txt, subtask0_sample-04.txt, subtask0_sample-05.txt
All subtask0_sample-01.txt, subtask0_sample-02.txt, subtask0_sample-03.txt, subtask0_sample-04.txt, subtask0_sample-05.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt
Case Name Status Exec Time Memory
subtask0_sample-01.txt AC 415 ms 72812 KB
subtask0_sample-02.txt AC 293 ms 64236 KB
subtask0_sample-03.txt AC 294 ms 64236 KB
subtask0_sample-04.txt AC 288 ms 64236 KB
subtask0_sample-05.txt AC 290 ms 64236 KB
subtask1_01.txt AC 286 ms 64236 KB
subtask1_02.txt AC 284 ms 64236 KB
subtask1_03.txt AC 281 ms 64236 KB
subtask1_04.txt AC 309 ms 66156 KB
subtask1_05.txt AC 319 ms 66924 KB
subtask1_06.txt AC 345 ms 69228 KB
subtask1_07.txt AC 293 ms 64876 KB
subtask1_08.txt AC 312 ms 65772 KB
subtask1_09.txt AC 1218 ms 72168 KB
subtask1_10.txt AC 460 ms 71528 KB
subtask1_11.txt AC 1151 ms 70232 KB
subtask1_12.txt AC 1150 ms 70360 KB
subtask1_13.txt AC 1147 ms 70360 KB
subtask1_14.txt AC 1165 ms 70120 KB
subtask1_15.txt AC 1178 ms 71144 KB
subtask1_16.txt AC 1097 ms 70232 KB
subtask1_17.txt AC 1007 ms 70376 KB
subtask1_18.txt AC 282 ms 64236 KB
subtask1_19.txt AC 298 ms 65900 KB
subtask1_20.txt AC 1262 ms 68696 KB