Submission #1752806
Source Code Expand
import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = float("inf")
sys.setrecursionlimit(10**7)
# 4近傍(右, 下, 左, 上)
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W
class CumulativeSum2dim:
def __init__(self, field: list):
self.h = len(field)
self.w = len(field[0])
self.dp = [[0] * (self.w + 1) for _ in range(self.h + 1)]
for y in range(self.h):
for x in range(self.w):
self.dp[y + 1][x + 1] = field[y][x] + self.dp[y + 1][x]
for x in range(self.w):
self.dp[y + 1][x + 1] += self.dp[y][x + 1]
# 左上(y1, x1)から右下(y2, x2)の合計を返す.(y2, x2)は含まない
# 座標はmemoを作成したboard準拠
# (ex, sum(0, 0, 2, 2)なら(0, 0), (0, 1), (1, 0), (1, 1)の合計を返す)
def total(self, y1, x1, y2, x2):
return self.dp[y2][x2] - self.dp[y2][x1] - self.dp[y1][x2] + self.dp[y1][x1]
def main():
H, W = map(int, input().split())
field_w = [[0] * W for _ in range(H)]
field_b = [[0] * W for _ in range(H)]
for y in range(H):
line = list(map(int, input().split()))
for x in range(W):
if (y + x) % 2 == 0:
field_b[y][x] = line[x]
else:
field_w[y][x] = line[x]
cw = CumulativeSum2dim(field_w)
cb = CumulativeSum2dim(field_b)
ans = 0
for y1 in range(H):
for x1 in range(W):
for y2 in range(H + 1):
for x2 in range(W + 1):
white = cw.total(y1, x1, y2, x2)
black = cb.total(y1, x1, y2, x2)
if white == black:
ans = max(ans, (y2 - y1) * (x2 - x1))
print(ans)
if __name__ == '__main__':
main()
Submission Info
Submission Time |
|
Task |
B - チョコレート |
User |
MitI_7 |
Language |
Python (3.4.3) |
Score |
0 |
Code Size |
2049 Byte |
Status |
TLE |
Exec Time |
2104 ms |
Memory |
4320 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 100 |
Status |
|
|
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 |
23 ms |
3316 KB |
subtask0_sample-02.txt |
AC |
23 ms |
3424 KB |
subtask0_sample-03.txt |
AC |
24 ms |
3316 KB |
subtask0_sample-04.txt |
AC |
24 ms |
3316 KB |
subtask0_sample-05.txt |
AC |
23 ms |
3316 KB |
subtask1_01.txt |
AC |
23 ms |
3316 KB |
subtask1_02.txt |
AC |
23 ms |
3316 KB |
subtask1_03.txt |
AC |
24 ms |
3316 KB |
subtask1_04.txt |
AC |
30 ms |
3316 KB |
subtask1_05.txt |
AC |
127 ms |
3424 KB |
subtask1_06.txt |
AC |
407 ms |
3316 KB |
subtask1_07.txt |
AC |
29 ms |
3316 KB |
subtask1_08.txt |
AC |
83 ms |
3316 KB |
subtask1_09.txt |
TLE |
2104 ms |
3936 KB |
subtask1_10.txt |
TLE |
2104 ms |
3424 KB |
subtask1_11.txt |
TLE |
2103 ms |
4320 KB |
subtask1_12.txt |
TLE |
2104 ms |
4320 KB |
subtask1_13.txt |
TLE |
2103 ms |
4320 KB |
subtask1_14.txt |
TLE |
2104 ms |
3936 KB |
subtask1_15.txt |
TLE |
2104 ms |
3936 KB |
subtask1_16.txt |
TLE |
2103 ms |
4320 KB |
subtask1_17.txt |
TLE |
2103 ms |
3808 KB |
subtask1_18.txt |
AC |
23 ms |
3316 KB |
subtask1_19.txt |
AC |
92 ms |
3424 KB |
subtask1_20.txt |
TLE |
2103 ms |
3680 KB |