Submission #1752834

---

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(y1 + 1, H + 1):
                for x2 in range(x1 + 1, 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

Judge Result