結果

問題 No.1247 ブロック登り
ユーザー tpynerivertpyneriver
提出日時 2020-10-19 19:38:04
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,346 bytes
コンパイル時間 559 ms
コンパイル使用メモリ 87,352 KB
実行使用メモリ 604,412 KB
最終ジャッジ日時 2023-09-28 13:22:15
合計ジャッジ時間 8,335 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 AC 74 ms
71,264 KB
testcase_02 AC 74 ms
71,264 KB
testcase_03 AC 72 ms
71,156 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 AC 71 ms
71,256 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 278 ms
81,508 KB
testcase_10 AC 284 ms
82,476 KB
testcase_11 TLE -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
readline = sys.stdin.readline

N, K = map(int, readline().split())

A = list(map(int, readline().split()))

INF = 10**9+7

De = [[-INF]*(N+1) for _ in range(N)]
Do = [[-INF]*(N+1) for _ in range(N)]

dpl = [[[-INF]*(N+1) for _ in range(N)] for _ in range(K)]
dpr = [[[-INF]*(N+1) for _ in range(N)] for _ in range(K)]

for i in range(N):
    dpl[0][i][i+1] = K*A[i]
    dpr[0][i][i+1] = K*A[i]


for t in range(0, K-1):
    for l in range(N):
        for r in range(l+1, min(l+t+2, N+1)):
            if dpl[t][l][r] == -INF:
                continue
            dl = dpl[t][l][r]
            dr = dpr[t][l][r]
            if t+2 < K and l+1 != r:
                dpl[t+2][l][r] = max(dpl[t+2][l][r], dl)
                dpr[t+2][l][r] = max(dpr[t+2][l][r], dr)
            
            if l != 0:
                dpl[t+1][l-1][r] = max(dpl[t+1][l-1][r], dl+(K-1-t)*A[l-1])
            if r != N:
                dpr[t+1][l][r+1] = max(dpr[t+1][l][r+1], dr+(K-1-t)*A[r])
            
            if t < t+r-l-1 < K:
                dpl[t+r-l-1][l][r] = max(dpl[t+r-l-1][l][r], dr)
                dpr[t+r-l-1][l][r] = max(dpr[t+r-l-1][l][r], dl)
            
            
            
            if l+1 != r:
                if (K-t)&1:
                    De[l][min(l+K-t, r)] = max(De[l][min(l+K-t, r)], dl)
                else:
                    Do[l][min(l+K-t, r)] = max(Do[l][min(l+K-t, r)], dl)

                if l <= r-K+t: 
                    De[r-K+t][r] = max(De[max(l, r-K+t)][r], dr)
                else:
                    if ((K-t)&1)^((r-l)&1):
                        De[max(l, r-K+t)][r] = max(De[max(l, r-K+t)][r], dr)
                    else:
                        Do[max(l, r-K+t)][r] = max(Do[max(l, r-K+t)][r], dr)
              
ans = [-INF]*N
for l in range(N):
    for r in range(l+1, N+1):
        ans[l] = max(ans[l], dpl[K-1][l][r])
        ans[r-1] = max(ans[r-1], dpr[K-1][l][r])

for l in range(N):
    for r in range(l+1, N+1):
        d = De[l][r]
        for i in range(l, r, 2):
            ans[i] = max(ans[i], d)
        d = Do[l][r]
        for i in range(l+1, r, 2):
            ans[i] = max(ans[i], d)


Ans = [-INF]*N

for i in range(N):
    if i > 0:
        Ans[i-1] = max(Ans[i-1], ans[i])
    if i < N-1:
        Ans[i+1] = max(Ans[i+1], ans[i])
print('\n'.join(map(str, Ans)))
0