結果
問題 |
No.2139 K Consecutive Sushi
|
ユーザー |
![]() |
提出日時 | 2025-03-20 20:26:54 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 152 ms / 2,000 ms |
コード長 | 1,335 bytes |
コンパイル時間 | 227 ms |
コンパイル使用メモリ | 82,468 KB |
実行使用メモリ | 109,880 KB |
最終ジャッジ日時 | 2025-03-20 20:28:30 |
合計ジャッジ時間 | 4,497 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
def main(): import sys from collections import deque N, K = map(int, sys.stdin.readline().split()) A = list(map(int, sys.stdin.readline().split())) prefix = [0] * (N + 1) for i in range(N): prefix[i+1] = prefix[i] + A[i] dp_not = [0] * (N+1) # dp_not[i]: max sum up to i-1, not taking i-1 taken = [0] * (N+1) max_taken_prev = 0 q = deque() q.append(-1) S = prefix for i in range(N): current_i = i j_start = current_i - K + 1 while q and q[0] < j_start: q.popleft() if q: best = dp_not[q[0] + 1] - S[q[0] + 1] else: best = -float('inf') # Compute taken_val if j_start <= -1: best = max(best, 0 - S[0]) # j = -1, which is allowed taken_val = best + S[i+1] taken[i+1] = taken_val # Update dp_not[i+1] new_dp_not = max(dp_not[i], max_taken_prev) dp_not[i+1] = new_dp_not # Update the deque with j = i current_H = new_dp_not - S[i+1] while q and (dp_not[q[-1]+1] - S[q[-1]+1] <= current_H): q.pop() q.append(i) max_taken_prev = taken_val print(max(dp_not[N], taken[N])) if __name__ == "__main__": main()