結果

問題 No.2509 Beam Shateki
ユーザー Theta
提出日時 2024-05-10 20:06:17
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 373 ms / 2,000 ms
コード長 1,915 bytes
コンパイル時間 243 ms
コンパイル使用メモリ 82,520 KB
実行使用メモリ 80,632 KB
最終ジャッジ日時 2024-12-20 04:10:55
合計ジャッジ時間 15,421 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 61
権限があれば一括ダウンロードができます

ソースコード

diff # 

from itertools import combinations, product
from typing import Any


def main():
    H, W = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(H)]
    beam_ranges: list[set[Any]] = []
    beam_sum: list[int] = []
    for i in range(H):
        mass = set()
        sum_ = 0
        for j in range(W):
            mass.add((i, j))
            sum_ += board[i][j]
        beam_ranges.append(mass)
        beam_sum.append(sum_)

    for j in range(W):
        mass = set()
        sum_ = 0
        for i in range(H):
            mass.add((i, j))
            sum_ += board[i][j]
        beam_ranges.append(mass)
        beam_sum.append(sum_)

    for i in range(H + W - 1):
        mass = set()
        sum_ = 0
        if i < H:
            cur_h = i
            cur_w = 0
        else:
            cur_h = H - 1
            cur_w = i - H + 1
        while cur_h >= 0 and cur_w < W:
            mass.add((cur_h, cur_w))
            sum_ += board[cur_h][cur_w]
            cur_h -= 1
            cur_w += 1
        beam_ranges.append(mass)
        beam_sum.append(sum_)

    for i in range(H + W - 1):
        mass = set()
        sum_ = 0
        if i < H:
            cur_h = H - 1 - i
            cur_w = 0
        else:
            cur_h = 0
            cur_w = i - H + 1
        while cur_h < H and cur_w < W:
            mass.add((cur_h, cur_w))
            sum_ += board[cur_h][cur_w]
            cur_h += 1
            cur_w += 1
        beam_ranges.append(mass)
        beam_sum.append(sum_)

    max_sum = max(beam_sum)

    for i, j in combinations(range(len(beam_ranges)), 2):
        tmp_sum = beam_sum[i] + beam_sum[j]
        multi = beam_ranges[i].intersection(beam_ranges[j])
        for multi_mass in multi:
            tmp_sum -= board[multi_mass[0]][multi_mass[1]]
        max_sum = max(max_sum, tmp_sum)
    print(max_sum)


if __name__ == "__main__":
    main()
0