結果

問題 No.5024 魔法少女うなと宝集め
コンテスト
ユーザー Koi
提出日時 2026-05-02 17:56:12
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 327 ms / 2,000 ms
コード長 2,710 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,017 ms
コンパイル使用メモリ 85,632 KB
実行使用メモリ 94,720 KB
スコア 1,869,399
最終ジャッジ日時 2026-05-02 17:59:28
合計ジャッジ時間 19,170 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_1
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# DPでやる
N, T = map(int, input().split())

A = [list(map(int, input().split())) for _ in range(N)]

DP = [[[-1] * N for _ in range(N)] for _ in range(T)]
DP_end = [[(-1,-1, -1) for _ in range(N)] for _ in range(N)]
Pre = [[[(-1,-1,-1)] * N for _ in range(N)] for _ in range(T)]
for i in range(N):
    for j in range(N):
        DP[0][i][j] = A[i][j]
# DP[t][i][j]:=tターン目で、座標(i,j)にいて、i以降の座標には(i,j)を除いてどれも訪れてない時のスコアのMAX

for t in range(T):
    for i in range(N):
        for j in range(N):
            if(DP[t][i][j] < 0):
                continue
            v = 0
            for k in range(j - 1, -1, -1):
                v += A[i][k]
                # (i,k)まで行く。
                nxt_t = t +abs(j - k)
                if(nxt_t < T):
                    if(DP_end[i][k][1] < DP[t][i][j] + v):
                        DP_end[i][k] = (nxt_t, DP[t][i][j] + v)
                # (i + 1,k)に行く。
                nxt_t += 1
                if(nxt_t < T):
                    if(i < N - 1 and DP[nxt_t][i + 1][k] < DP[t][i][j] + v + A[i + 1][k]):
                        DP[nxt_t][i + 1][k] = DP[t][i][j] + v + A[i + 1][k]
                        Pre[nxt_t][i + 1][k ] = (t, i, j)
            v = 0
            for k in range(j, N):
                if(k != j):
                    v += A[i][k]
                # (i,k)まで行く。
                nxt_t = t +abs(j - k)
                if(nxt_t < T):
                    if(DP_end[i][k][1] < DP[t][i][j] + v):
                        DP_end[i][k] = (nxt_t, DP[t][i][j] + v)
                # (i + 1,k)に行く。
                nxt_t += 1
                if(nxt_t < T):
                    if(i < N - 1 and DP[nxt_t][i + 1][k] < DP[t][i][j] + v + A[i + 1][k]):
                        DP[nxt_t][i + 1][k] = DP[t][i][j] + v + A[i + 1][k]
                        Pre[nxt_t][i + 1][k ] = (t, i, j)
best_i = -1
best_j = -1
best_t = -1
best_score = 0
for i in range(N):
    for j in range(N):
        if(DP_end[i][j][1] > best_score):
            best_i = i
            best_j = j
            best_t = DP_end[i][j][0]
            best_score = DP_end[i][j][1]

# print(best_i,best_j)
Ans = [(best_i, best_j)]
i = best_i
j = best_j
t = best_t
while True:
    nt, ni, nj = Pre[t][i][j]
    if(nt == -1):
        break
    # print(nt,ni,nj,t,i,j)
    if(ni == i - 1):
        if(j <= nj):
           for k in range(j, nj + 1):
               Ans.append((ni, k))
        else:
           for k in range(j, nj - 1, -1):
               Ans.append((ni, k))
    t,i,j = nt,ni,nj
    # (ni-1,nj)から(ni,j)に行き、(i,j)についた。

print(len(Ans))
for l in Ans:
    print(*l)
0