結果
問題 |
No.1248 Kth Sum
|
ユーザー |
![]() |
提出日時 | 2025-06-12 15:30:54 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,172 bytes |
コンパイル時間 | 471 ms |
コンパイル使用メモリ | 82,108 KB |
実行使用メモリ | 168,652 KB |
最終ジャッジ日時 | 2025-06-12 15:32:18 |
合計ジャッジ時間 | 5,337 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 1 |
other | AC * 1 WA * 13 TLE * 1 -- * 21 |
ソースコード
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()