結果

問題 No.2139 K Consecutive Sushi
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:26:54
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 152 ms / 2,000 ms
コード長 1,335 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 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
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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()
0