Submission #1752808
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 |
PyPy3 (2.4.0) |
Score |
0 |
Code Size |
2049 Byte |
Status |
TLE |
Exec Time |
2106 ms |
Memory |
45020 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 |
168 ms |
38684 KB |
subtask0_sample-02.txt |
AC |
173 ms |
38256 KB |
subtask0_sample-03.txt |
AC |
166 ms |
38256 KB |
subtask0_sample-04.txt |
AC |
170 ms |
38256 KB |
subtask0_sample-05.txt |
AC |
169 ms |
38256 KB |
subtask1_01.txt |
AC |
163 ms |
38256 KB |
subtask1_02.txt |
AC |
162 ms |
38256 KB |
subtask1_03.txt |
AC |
176 ms |
39536 KB |
subtask1_04.txt |
AC |
197 ms |
41200 KB |
subtask1_05.txt |
AC |
198 ms |
41200 KB |
subtask1_06.txt |
AC |
206 ms |
41200 KB |
subtask1_07.txt |
AC |
176 ms |
39280 KB |
subtask1_08.txt |
AC |
185 ms |
40176 KB |
subtask1_09.txt |
TLE |
2106 ms |
43500 KB |
subtask1_10.txt |
AC |
531 ms |
43628 KB |
subtask1_11.txt |
TLE |
2106 ms |
43500 KB |
subtask1_12.txt |
TLE |
2105 ms |
44176 KB |
subtask1_13.txt |
TLE |
2106 ms |
43500 KB |
subtask1_14.txt |
TLE |
2106 ms |
43500 KB |
subtask1_15.txt |
TLE |
2106 ms |
43500 KB |
subtask1_16.txt |
TLE |
2106 ms |
43500 KB |
subtask1_17.txt |
TLE |
2106 ms |
45020 KB |
subtask1_18.txt |
AC |
166 ms |
38256 KB |
subtask1_19.txt |
AC |
189 ms |
40048 KB |
subtask1_20.txt |
TLE |
2106 ms |
42860 KB |