結果
問題 |
No.2139 K Consecutive Sushi
|
ユーザー |
|
提出日時 | 2025-06-25 15:47:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 173 ms / 2,000 ms |
コード長 | 893 bytes |
コンパイル時間 | 481 ms |
コンパイル使用メモリ | 82,596 KB |
実行使用メモリ | 108,292 KB |
最終ジャッジ日時 | 2025-06-25 15:47:49 |
合計ジャッジ時間 | 4,661 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
import sys from collections import deque MI=lambda:map(int,sys.stdin.readline().split()) n,K=MI() A=list(MI()) # 窗口数 M=n-K+1 # dp[i] = 覆盖前 i 个窗口(0..i-1)的最小跳过代价 dp=[0]*(M+1) # B[j] = 在位置 j 跳过的总代价候选 = dp[ max(0, j-K+1) ] + A[j] B=[0]*n dq=deque() # 初始化窗0 时的候选 j∈[0..K-1] for j in range(K): B[j]=A[j] while dq and B[dq[-1]]>=B[j]: dq.pop() dq.append(j) # 依次算 dp[1]..dp[M] for w in range(M): # 用当前窗口 [w..w+K-1] 内最小的 B 作为 dp[w+1] dp[w+1]=B[dq[0]] # 滑出左端点 j=w if dq[0]==w: dq.popleft() # 加入新点 j=w+K nj=w+K if nj<n: idx=nj-K+1 if idx<0: idx=0 B[nj]=dp[idx]+A[nj] while dq and B[dq[-1]]>=B[nj]: dq.pop() dq.append(nj) # 总美味 - 最小跳过代价 print(sum(A)-dp[M])