結果
問題 |
No.704 ゴミ拾い Medium
|
ユーザー |
![]() |
提出日時 | 2018-06-16 02:44:00 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 372 ms / 1,500 ms |
コード長 | 1,978 bytes |
コンパイル時間 | 608 ms |
コンパイル使用メモリ | 67,876 KB |
実行使用メモリ | 16,248 KB |
最終ジャッジ日時 | 2024-06-30 16:00:48 |
合計ジャッジ時間 | 10,169 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 44 |
ソースコード
#include<iostream> #include<vector> #include<algorithm> using namespace std; #define rep(i,n) for(int i=0;i<(n);i++) struct SegmentTree{ int n=1, inf=1e8; vector<int> seg; SegmentTree(int m){ while(n<m) n*=2; seg.resize(n*2-1, inf); } void update(int i, int x){ i+=n-1; seg[i]=x; while(i>0){ i=(i-1)/2; seg[i]=min(seg[i*2+1], seg[i*2+2]); } } int getmin(int ql, int qr){ return getmin(ql, qr, 0, 0, n); } int getmin(int ql, int qr, int i, int il, int ir){ if(qr<=il || ir<=ql) return inf; if(ql<=il && ir<=qr) return seg[i]; int m=(ir+il)/2; int vl=getmin(ql, qr, i*2+1, il, m), vr=getmin(ql, qr, i*2+2, m, ir); return min(vl, vr); } }; void chmin(int &l, int r){if(l>r)l=r;} int main(){ int n; cin>> n; vector<int> a(n+1); rep(i, n) cin>> a[i+1]; vector<int> x(n+1); rep(i, n) cin>> x[i+1]; vector<int> y(n+1); rep(i, n) cin>> y[i+1]; const int inf=1e8; SegmentTree seg_l(n), seg_r(n); // seg_l <- -x[k]+y[k]が入ってる // seg_r <- x[k]+y[k]が入ってる vector<int> dp(n+1, inf); dp[0]=0; for(int i=1, j=1; i<=n; i++){ // j := 人(i-1)より右にあるゴミで最も近いもののindex // chmin(dp[i], dp[i-1]+abs(a[i]-x[i])+y[i]); // chmin(dp[i], seg_l.getmin(0, i)+a[i]); // chmin(dp[i], seg_r.getmin(0, i)-a[i]); // seg_r.update(i-1, x[i]+y[i]+dp[i-1]); seg_r.update(i-1, x[i]+y[i]+dp[i-1]); while(j<=i && x[j]<=a[i]){ seg_l.update(j-1, -x[j]+y[j]+dp[j-1]); seg_r.update(j-1, inf); j++; } dp[i]=dp[i-1]+abs(a[i]-x[i])+y[i]; chmin(dp[i], seg_l.getmin(0, i)+a[i]); chmin(dp[i], seg_r.getmin(0, i)-a[i]); // while(j<=i && x[j]<=a[i]){ // // 人(i-1)と人iの間にあったゴミたちを... // seg_l.update(j-1, -x[j]+y[j]+dp[j-1]); // seg_r.update(j-1, inf); // j++; // } } cout<< dp[n]<< endl; return 0; }