結果
問題 | No.2859 Falling Balls |
ユーザー |
![]() |
提出日時 | 2024-08-26 13:59:24 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 202 ms / 3,000 ms |
コード長 | 1,035 bytes |
コンパイル時間 | 2,453 ms |
コンパイル使用メモリ | 209,168 KB |
最終ジャッジ日時 | 2025-02-24 02:16:00 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/segtree> using namespace std; long op(long a, long b){return max(a,b);} long e(){return -1L<<60;} int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N,K; cin>>N>>K; vector<long>T(N),X(N),C(N); for(long &t:T)cin>>t,t*=K; for(long &x:X)cin>>x; for(long &c:C)cin>>c; vector<long>xs(N),ys(N); for(int i=0;i<N;i++) { xs[i]=T[i]-X[i]; ys[i]=T[i]+X[i]; } vector<int>ord(N); iota(ord.begin(),ord.end(),0); sort(ord.begin(),ord.end(),[&](int i, int j) { return make_pair(xs[i],ys[i])<make_pair(xs[j],ys[j]); }); auto B=ys; sort(B.begin(),B.end()); B.erase(unique(B.begin(),B.end()),B.end()); atcoder::segtree<long,op,e>seg(B.size()+1); seg.set(0,0); for(int i:ord) { long x=xs[i],y=ys[i]; if(x<0||y<0)continue; y=lower_bound(B.begin(),B.end(),y)-B.begin(); seg.set(y,max(0L,seg.prod(0,y+1))+C[i]); } cout<<seg.all_prod()<<endl; }