結果

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

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:2+N]))
    
    dp_prev = {0: 0}
    
    for i in range(N):
        dp_current = {}
        a = A[i]
        for u_prev, sum_prev in dp_prev.items():
            # Option 1: exclude A[i]
            u_new = u_prev + 1
            if u_new in dp_current:
                if sum_prev < dp_current[u_new]:
                    dp_current[u_new] = sum_prev
            else:
                dp_current[u_new] = sum_prev
            
            # Option 2: include A[i]
            if u_prev >= K-1:
                u_new2 = u_prev - (K-1)
                sum_new2 = sum_prev + a
                if u_new2 in dp_current:
                    if sum_new2 < dp_current[u_new2]:
                        dp_current[u_new2] = sum_new2
                else:
                    dp_current[u_new2] = sum_new2
        
        # Update dp_prev for the next iteration
        dp_prev = dp_current
    
    # The minimal sum is the value where u=0
    print(dp_prev.get(0, float('inf')))
    
if __name__ == '__main__':
    main()
0