結果
問題 | No.1247 ブロック登り |
ユーザー | 👑 SPD_9X2 |
提出日時 | 2020-10-03 17:50:24 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,839 bytes |
コンパイル時間 | 275 ms |
コンパイル使用メモリ | 87,224 KB |
実行使用メモリ | 85,452 KB |
最終ジャッジ日時 | 2023-09-25 05:32:39 |
合計ジャッジ時間 | 8,265 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 71 ms
71,140 KB |
testcase_01 | AC | 71 ms
71,284 KB |
testcase_02 | AC | 73 ms
71,460 KB |
testcase_03 | AC | 69 ms
71,516 KB |
testcase_04 | AC | 100 ms
77,000 KB |
testcase_05 | AC | 89 ms
76,392 KB |
testcase_06 | AC | 70 ms
71,332 KB |
testcase_07 | AC | 369 ms
84,292 KB |
testcase_08 | AC | 376 ms
85,452 KB |
testcase_09 | AC | 280 ms
81,360 KB |
testcase_10 | AC | 315 ms
82,716 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 | -- | - |
ソースコード
""" https://yukicoder.me/problems/no/1246 最終的に使う範囲は区間になる 終点を決めたとする l,rでdp? l,r,0→l,rの区間でどこにいるか 300*300*2*300 最後をどうするかが問題 偶奇別にセグ木を持って更新? O(N*N*K*logN) ? ====解説を見た==== 区間の間の移動は関係ない →偶数回とどまった後に端に移動するという移動に一元化可能 →始点の問題も解決できる dp[今いる端][今いない端][高さ] = スコアの最大値 で解ける """ from sys import stdin N,K = map(int,stdin.readline().split()) A = list(map(int,stdin.readline().split())) ans = [float("-inf")] * N dp = [[ [float("-inf")] * (K+1) for i in range(N)] for j in range(N)] for i in range(N): dp[i][i][K] = K * A[i] for k in range(K,-1,-1): for a in range(N): for b in range(N): if k == 0: ans[a] = max(dp[a][b][k] , ans[a]) continue if k-2 >= 0 and a != b: dp[a][b][k-2] = max(dp[a][b][k-2] , dp[a][b][k]) if a <= b: #端を拡張 if a-1 >= 0: dp[a-1][b][k-1] = max(dp[a-1][b][k-1] , dp[a][b][k] + (k-1)*A[a-1] ) if a+k <= b: ans[a+k] = max(ans[a+k] , dp[a][b][k]) if b-a <= k and a != b: dp[b][a][k-(b-a)] = max(dp[b][a][k-(b-a)] , dp[a][b][k]) if a >= b: if a+1 < N: dp[a+1][b][k-1] = max(dp[a+1][b][k-1] , dp[a][b][k] + (k-1)*A[a+1]) if a-k >= b: ans[a-k] = max(ans[a-k] , dp[a][b][k]) if a-b <= k and a != b: dp[b][a][k-(a-b)] = max(dp[b][a][k-(a-b)] , dp[a][b][k]) print ("\n".join(map(str,ans)))