結果
問題 |
No.1248 Kth Sum
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()