結果

問題 No.2509 Beam Shateki
ユーザー ntuda
提出日時 2023-10-29 21:10:19
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,709 bytes
コンパイル時間 402 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 86,276 KB
最終ジャッジ日時 2024-09-25 16:54:32
合計ジャッジ時間 14,103 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 TLE * 1 -- * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

H, W = map(int, input().split())
A = [[0] * (W + 2)]
A += [[0] + list(map(int, input().split())) + [0] for _ in range(H)]
A += [[0] * (W + 2)]
H += 2
W += 2

N = (H + W) * 9 * 2
D = []
for i in range(-1, 2):
    for j in range(-1, 2):
        D.append((i, j))
dic = {}
for i, (x, y) in enumerate(D):
    dic[(-x, -y)] = i
ans = 0


def HWC(x):
    if x < H * 9:
        return (x // 9, 0)
    x -= H * 9
    if x < H * 9:
        return (x // 9, W - 1)
    x -= H * 9
    if x < W * 9:
        return (0, x // 9)
    x -= W * 9
    return (H - 1, x // 9)


Q = set()
for i in range(N - 1):
    if i in Q:
        continue
    x, y = HWC(i)
    cnt1 = 0
    P = set()
    dx, dy = D[i % 9]
    x += dx
    y += dy
    while 0 <= x < H and 0 <= y < W and A[x][y] > 0:
        cnt1 += A[x][y]
        P.add((x, y))
        x += dx
        y += dy
    if y == W - 1:
        Q.add((H + y) * 9 + dic[(dx, dy)])
    elif x == 0:
        Q.add((2 * H + x) * 9 + dic[(dx, dy)])
    elif x == H - 1:
        Q.add((2 * H + W + x) * 9 + dic[(dx, dy)])
    for j in range(i + 1, N):
        if j in Q:
            continue
        x, y = HWC(j)
        cnt2 = 0
        dx, dy = D[j % 9]
        x += dx
        y += dy
        while 0 <= x < H and 0 <= y < W and A[x][y] > 0:
            if (x, y) not in P:
                cnt2 += A[x][y]
            x += dx
            y += dy
        if y == W - 1:
            Q.add((H + y) * 9 + dic[(dx, dy)])
        elif x == 0:
            Q.add((2 * H + x) * 9 + dic[(dx, dy)])
        elif x == H - 1:
            Q.add((2 * H + W + x) * 9 + dic[(dx, dy)])
        ans = max(ans, cnt1 + cnt2)
        # print(i, HWC(i), D[i % 9], j, HWC(j), D[j % 9], cnt1, cnt2)
print(ans)
0