結果

問題 No.1248 Kth Sum
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:34:48
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,002 bytes
コンパイル時間 439 ms
コンパイル使用メモリ 81,772 KB
実行使用メモリ 109,880 KB
最終ジャッジ日時 2025-06-12 20:35:20
合計ジャッジ時間 6,156 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other WA * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    N, K = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    A = [0] + A  # Convert to 1-based index

    dp = [float('inf')] * (N + 1)
    dp[0] = 0  # Base case

    dq = deque()

    for i in range(1, N + 1):
        s = i - K
        if s >= 0:
            # Calculate f(s) = dp[s] + A[s + K]
            f_s = dp[s] + A[s + K]  # since A is 1-based
            # Maintain deque in increasing order of f(s)
            while dq and (dp[dq[-1]] + A[dq[-1] + K] >= f_s):
                dq.pop()
            dq.append(s)
        
        # Remove elements from the front that are out of the window
        while dq and dq[0] < (i - K + 1):
            dq.popleft()
        
        if i >= K:
            if dq:
                min_s = dq[0]
                dp[i] = dp[min_s] + A[min_s + K]
            # else, dp[i] remains infinity (invalid)

    print(dp[N])

if __name__ == "__main__":
    main()
0