結果
問題 | No.1375 Divide and Update |
ユーザー | 👑 SPD_9X2 |
提出日時 | 2021-02-05 21:56:28 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 337 ms / 2,000 ms |
コード長 | 942 bytes |
コンパイル時間 | 365 ms |
コンパイル使用メモリ | 87,112 KB |
実行使用メモリ | 156,152 KB |
最終ジャッジ日時 | 2023-09-15 08:07:23 |
合計ジャッジ時間 | 6,611 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 73 ms
71,048 KB |
testcase_01 | AC | 73 ms
71,436 KB |
testcase_02 | AC | 71 ms
71,456 KB |
testcase_03 | AC | 75 ms
71,420 KB |
testcase_04 | AC | 72 ms
71,328 KB |
testcase_05 | AC | 72 ms
71,448 KB |
testcase_06 | AC | 72 ms
71,360 KB |
testcase_07 | AC | 72 ms
71,004 KB |
testcase_08 | AC | 73 ms
71,180 KB |
testcase_09 | AC | 72 ms
71,352 KB |
testcase_10 | AC | 287 ms
138,576 KB |
testcase_11 | AC | 296 ms
140,536 KB |
testcase_12 | AC | 209 ms
106,204 KB |
testcase_13 | AC | 198 ms
102,244 KB |
testcase_14 | AC | 315 ms
147,660 KB |
testcase_15 | AC | 312 ms
147,456 KB |
testcase_16 | AC | 319 ms
147,396 KB |
testcase_17 | AC | 278 ms
128,504 KB |
testcase_18 | AC | 271 ms
130,020 KB |
testcase_19 | AC | 270 ms
130,308 KB |
testcase_20 | AC | 337 ms
156,152 KB |
ソースコード
""" 差分を考える 区間をXに置き換えるので 耳dpで解ける dp[i][state] = 最大の寄与 state = 0 #始まっていない → 0 state = 1 #Xに置き換えている state = 2 #区間が終了している """ import sys from sys import stdin N,X,Y = map(int,stdin.readline().split()) a = list(map(int,stdin.readline().split())) dpL = [[0,float("-inf"),float("-inf")] for i in range(N)] for i in range(N): if i == 0: dpL[i][1] = X-a[i] else: dpL[i][1] = max(dpL[i-1][0] , dpL[i-1][1]) + X-a[i] dpL[i][2] = max(dpL[i-1][1] , dpL[i-1][2]) a.reverse() dpR = [[0,float("-inf"),float("-inf")] for i in range(N)] for i in range(N): if i == 0: dpR[i][1] = Y-a[i] else: dpR[i][1] = max(dpR[i-1][0] , dpR[i-1][1]) + Y-a[i] dpR[i][2] = max(dpR[i-1][1] , dpR[i-1][2]) dpR.reverse() s = sum(a) for i in range(1,N-1): print (s + dpL[i][2] + dpR[i][2])