제출 #754297

#제출 시각아이디문제언어결과실행 시간메모리
754297bgnbvnbvSalesman (IOI09_salesman)C++14
80 / 100
577 ms46636 KiB
#include<bits/stdc++.h> #define TASKNAME "codeforce" #define pb push_back #define pli pair<ll,ll> #define fi first #define se second #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); using namespace std; using ll=long long; const ll maxN=5e5+10; const ll inf=1e18; const ll mod=1e9+7; struct node { ll be ,lon; node () { be=-inf; lon=-inf; } node operator+(const node&o) { node ans; ans.be=max(be,o.be); ans.lon=max(lon,o.lon); return ans; } }st[4*maxN]; ll o,u,d; void update(ll pos,ll val,ll id=1,ll l=1,ll r=o) { if(l==r) { st[id].lon=val-pos*u; st[id].be=val+pos*d; return; } ll mid=l+r>>1; if(pos<=mid) update(pos,val,id*2,l,mid); else update(pos,val,id*2+1,mid+1,r); st[id]=st[id*2]+st[id*2+1]; } node get(ll i,ll j,ll id=1,ll l=1,ll r=o) { if(j<l||r<i) return node(); if(i<=l&&r<=j) return st[id]; ll mid=l+r>>1; return get(i,j,id*2,l,mid)+get(i,j,id*2+1,mid+1,r); } ll n,s; struct qq { ll t,l,m; bool operator<(const qq&o) { return t<o.t; } }e[maxN]; pli a[maxN]; ll val[maxN],pre[maxN],luu[maxN]; void solve() { cin >> n >> u >> d >> s; o=s; for(int i=1;i<=n;i++) { cin >> e[i].t >> e[i].l >> e[i].m; o=max(o,e[i].l); } n++; e[n].t=inf; e[n].l=s; e[n].m=0; sort(e+1,e+n+1); ll ans=0; update(s,0); for(int i=1;i<=n;i++) { ll j=i; while(j<=n&&e[j].t==e[i].t) { a[j-i+1]={e[j].l,e[j].m}; j++; } sort(a+1,a+j-i+1); for(int k=1;k<=j-i;k++) { val[k]=max(get(a[k].fi+1,o).lon+a[k].fi*u+a[k].se,get(1,a[k].fi-1).be-a[k].fi*d+a[k].se); val[k]=max(val[k],-inf); pre[k]=pre[k-1]+a[k].se; luu[k]=val[k]; } ll mx=-inf; // theo chieu cung huong // bat dau tai j val[j]+pre[i]-pre[j]-(a[i].fi-a[j].fi)*u=val[j]-pre[j]+a[j].fi*u+pre[i]-a[i].fi*u for(int k=2;k<=j-i;k++) { mx=max(mx,val[k-1]-pre[k-1]+a[k-1].fi*d); luu[k]=max(luu[k],pre[k]-a[k].fi*d+mx); } // nguoc huong // val[j]+pre[j-1]-pre[i-1]-(a[j].fi-a[i].fi)*d=val[j]+pre[j-1]-a[j].fi*d-pre[i-1]+a[i].fi*d mx=-inf; for(int k=j-i-1;k>=1;k--) { ll vv=k+1; mx=max(mx,val[vv]+pre[vv-1]-a[vv].fi*u); luu[k]=max(luu[k],-pre[k-1]+a[k].fi*u+mx); } for(int k=1;k<=j-i;k++) { update(a[k].fi,luu[k]); } if(i==n) cout << luu[1]; i=j-1; } //cout << ans; } int main() { fastio //freopen(TASKNAME".INP","r",stdin); //freopen(TASKNAME".OUT","w",stdout); solve(); }

컴파일 시 표준 에러 (stderr) 메시지

salesman.cpp: In function 'void update(ll, ll, ll, ll, ll)':
salesman.cpp:38:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     ll mid=l+r>>1;
      |            ~^~
salesman.cpp: In function 'node get(ll, ll, ll, ll, ll)':
salesman.cpp:47:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |     ll mid=l+r>>1;
      |            ~^~
salesman.cpp: In function 'void solve()':
salesman.cpp:75:8: warning: unused variable 'ans' [-Wunused-variable]
   75 |     ll ans=0;
      |        ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...