結果
問題 | No.1375 Divide and Update |
ユーザー |
|
提出日時 | 2021-02-05 21:36:59 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 168 ms / 2,000 ms |
コード長 | 1,073 bytes |
コンパイル時間 | 222 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 114,576 KB |
最終ジャッジ日時 | 2024-07-02 11:48:48 |
合計ジャッジ時間 | 4,562 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 19 |
ソースコード
N,X,Y = map(int,input().split()) A = list(map(int,input().split())) imos = [A[i] for i in range(N)] for i in range(1,N): imos[i] += imos[i-1] dp = [0 for i in range(N)] dp_last = [0 for i in range(N)] dp[0] = max(A[0],X) dp_last[0] = max(imos[0],X) for i in range(1,N): dp[i] = max(dp[i-1]+A[i],dp_last[i-1]+X) dp_last[i] = max(imos[i],dp_last[i-1]+X) dp_back = [0 for i in range(N)] dp_back_last = [0 for i in range(N)] dp_back[-1] = max(A[-1],Y) dp_back_last[-1] = max(A[-1],Y) for i in range(N-2,-1,-1): dp_back[i] = max(dp_back[i+1]+A[i],dp_back_last[i+1]+Y) dp_back_last[i] = max(imos[-1]-imos[i]+A[i],dp_back_last[i+1]+Y) left = [A[i] for i in range(N)] right = [A[i] for i in range(N)] for i in range(1,N): left[i] = min(left[i-1],left[i]) for i in range(N-2,-1,-1): right[i] = min(right[i],right[i+1]) for i in range(1,N-1): x,y = dp[i-1],dp_back[i+1] if x==imos[i-1]: x = imos[i-1] - left[i-1] + X if y==imos[-1]-imos[i+1]+A[i+1]: y = imos[-1]-imos[i+1]+A[i+1] - right[i+1] + Y print(A[i]+x+y)