結果

問題 No.2509 Beam Shateki
ユーザー ThetaTheta
提出日時 2024-05-10 20:06:17
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 362 ms / 2,000 ms
コード長 1,915 bytes
コンパイル時間 438 ms
コンパイル使用メモリ 82,404 KB
実行使用メモリ 80,612 KB
最終ジャッジ日時 2024-05-10 20:06:34
合計ジャッジ時間 14,782 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 59 ms
67,344 KB
testcase_01 AC 59 ms
68,120 KB
testcase_02 AC 56 ms
68,604 KB
testcase_03 AC 113 ms
78,848 KB
testcase_04 AC 119 ms
79,036 KB
testcase_05 AC 116 ms
78,860 KB
testcase_06 AC 112 ms
78,968 KB
testcase_07 AC 115 ms
78,900 KB
testcase_08 AC 113 ms
79,056 KB
testcase_09 AC 114 ms
79,036 KB
testcase_10 AC 137 ms
78,844 KB
testcase_11 AC 115 ms
78,976 KB
testcase_12 AC 114 ms
79,136 KB
testcase_13 AC 333 ms
80,180 KB
testcase_14 AC 325 ms
80,052 KB
testcase_15 AC 353 ms
80,392 KB
testcase_16 AC 330 ms
80,328 KB
testcase_17 AC 331 ms
80,280 KB
testcase_18 AC 329 ms
80,128 KB
testcase_19 AC 356 ms
80,144 KB
testcase_20 AC 333 ms
80,052 KB
testcase_21 AC 336 ms
80,124 KB
testcase_22 AC 334 ms
80,068 KB
testcase_23 AC 358 ms
80,348 KB
testcase_24 AC 339 ms
80,280 KB
testcase_25 AC 335 ms
80,344 KB
testcase_26 AC 360 ms
80,148 KB
testcase_27 AC 333 ms
80,208 KB
testcase_28 AC 338 ms
80,112 KB
testcase_29 AC 338 ms
80,280 KB
testcase_30 AC 362 ms
80,336 KB
testcase_31 AC 329 ms
80,612 KB
testcase_32 AC 324 ms
80,264 KB
testcase_33 AC 75 ms
78,124 KB
testcase_34 AC 140 ms
79,244 KB
testcase_35 AC 204 ms
79,388 KB
testcase_36 AC 134 ms
78,792 KB
testcase_37 AC 76 ms
78,256 KB
testcase_38 AC 113 ms
78,920 KB
testcase_39 AC 105 ms
78,792 KB
testcase_40 AC 150 ms
79,404 KB
testcase_41 AC 61 ms
72,828 KB
testcase_42 AC 121 ms
79,052 KB
testcase_43 AC 228 ms
79,748 KB
testcase_44 AC 253 ms
79,924 KB
testcase_45 AC 118 ms
78,884 KB
testcase_46 AC 128 ms
79,012 KB
testcase_47 AC 256 ms
80,048 KB
testcase_48 AC 127 ms
79,216 KB
testcase_49 AC 163 ms
79,148 KB
testcase_50 AC 179 ms
79,476 KB
testcase_51 AC 75 ms
77,772 KB
testcase_52 AC 154 ms
79,024 KB
testcase_53 AC 57 ms
67,632 KB
testcase_54 AC 56 ms
68,908 KB
testcase_55 AC 58 ms
68,320 KB
testcase_56 AC 57 ms
68,872 KB
testcase_57 AC 58 ms
68,316 KB
testcase_58 AC 56 ms
68,328 KB
testcase_59 AC 57 ms
67,904 KB
testcase_60 AC 57 ms
69,040 KB
testcase_61 AC 58 ms
67,688 KB
testcase_62 AC 58 ms
67,968 KB
testcase_63 AC 58 ms
68,268 KB
権限があれば一括ダウンロードができます

ソースコード

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