제출 #1135040

#제출 시각아이디문제언어결과실행 시간메모리
1135040ByeWorldSalesman (IOI09_salesman)C++20
63 / 100
442 ms43420 KiB
#include <bits/stdc++.h> #define int long long #define ll long long #define pb push_back #define fi first #define se second #define lf (id<<1) #define rg ((id<<1)|1) #define md ((l+r)>>1) #define ld long double using namespace std; typedef pair<int,int> pii; typedef pair<char,char> pcc; typedef pair<int,pii> ipii; typedef pair<pii,pii> ipiii; const int MAXN = 5e5+30; const int SQRT = 610; const int MAXA = 5e5+10; const int MOD = 1e6+7; const int INF = 1e18+10; const int LOG = 21; const ld EPS = 1e-12; void chmx(int &a, int b){ a = max(a,b); } int n, u, d, s; vector <ipii> vec; struct seg { int st[4*MAXN]; void bd(int id, int l, int r){ st[id] = -INF; if(l==r) return; bd(lf,l,md); bd(rg,md+1,r); } int que(int id, int l, int r, int x, int y){ if(x<=l && r<=y) return st[id]; if(r<x || y<l) return -INF; return max(que(lf,l,md,x,y), que(rg,md+1,r,x,y)); } int upd(int id, int l,int r,int x,int p){ if(l==r && l==x){ chmx(st[id], p); return st[id]; } if(r<x || x<l) return st[id]; return st[id] = max(upd(lf,l,md,x,p), upd(rg,md+1,r,x,p)); } } LE, RI; int f[MAXN], f1[MAXN], f2[MAXN]; signed main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> u >> d >> s; for(int i=1; i<=MAXA; i++) f[i] = -INF; LE.bd(1,1,MAXA); RI.bd(1,1,MAXA); f[s] = 0; LE.upd(1,1,MAXA,s,d*s); RI.upd(1,1,MAXA,s,-u*s); // for(int i=1; i<=s-1; i++) dp[i] = -(s-i)*u; // -s*u + i*u // for(int i=s+1; i<=MAXA; i++) dp[i] = -(i-s)*d; // -i*d + s*d for(int i=1; i<=n; i++){ int d,id,w; cin>>d>>id>>w; vec.pb({d, {id,w}}); } vec.pb({MAXA, {s,0}}); sort(vec.begin(), vec.end()); for(int i=0; i<vec.size(); ){ int j = i; vector <pii> te; while(i<vec.size() && vec[i].fi == vec[j].fi){ te.pb({vec[i].se.fi, vec[i].se.se}); i++; } for(int j=0; j<te.size(); j++){ int p = te[j].fi; f1[p] = f2[p] = max(LE.que(1,1,MAXA,1,p)-d*p, RI.que(1,1,MAXA,p,MAXA)+u*p); } f2[te[0].fi] += te[0].se; f1[te.back().fi] += te.back().se; for(int j=1; j<te.size(); j++) chmx(f2[te[j].fi], f2[te[j-1].fi]-d*(te[j].fi-te[j-1].fi)+te[j].se); for(int j=(int)te.size()-2; j>=0; j--) chmx(f1[te[j].fi], f1[te[j+1].fi]-u*(te[j+1].fi-te[j].fi)+te[j].se); for(int j=0; j<te.size(); j++){ int p = te[j].fi; f[p] = max(f1[p], f2[p]); LE.upd(1,1,MAXA,p,f[p]+d*p); RI.upd(1,1,MAXA,p,f[p]-u*p); } } cout << f[s] << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...