結果
問題 |
No.704 ゴミ拾い Medium
|
ユーザー |
|
提出日時 | 2025-07-22 17:42:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 307 ms / 1,500 ms |
コード長 | 1,086 bytes |
コンパイル時間 | 558 ms |
コンパイル使用メモリ | 82,368 KB |
実行使用メモリ | 163,488 KB |
最終ジャッジ日時 | 2025-07-22 17:42:52 |
合計ジャッジ時間 | 9,563 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 44 |
ソースコード
import sys input=sys.stdin.readline MI=lambda:map(int,input().split()) li=lambda:list(MI()) ii=lambda:int(input()) n=ii() a=li() x=li() y=li() from collections import deque INF=10**30 dp=[0]*n dq=deque() # 存 (j, dp[j-1]+y[j]+x[j]) 的单调队列 px=0 # 指向下一个还未加入 s1 的 j s1=INF # 存 min(dp[j-1]+y[j]-x[j]) over 已加入的 j for i in range(n): prev=0 if i==0 else dp[i-1] v2=prev+y[i]+x[i] # 插入 v2 到单调队列 while dq and dq[-1][1]>=v2: dq.pop() dq.append((i,v2)) # 将所有 x[j] ≤ a[i] 的 j 加入 s1 前缀最小值 while px<=i and x[px]<=a[i]: pj=px prevj=0 if pj==0 else dp[pj-1] v1=prevj+y[pj]-x[pj] if v1<s1: s1=v1 px+=1 L=px # 弹出滑窗左端已经不满足 j≥L 的元素 while dq and dq[0][0]<L: dq.popleft() # 计算 dp[i] best=INF if s1<INF: v=s1+a[i] if v<best: best=v if dq: v=dq[0][1]-a[i] if v<best: best=v dp[i]=best print(dp[n-1])