제출 #874626

#제출 시각아이디문제언어결과실행 시간메모리
874626sjoonmin07Salesman (IOI09_salesman)C++17
60 / 100
502 ms58452 KiB
#include <bits/stdc++.h> #define fi first #define se second #define eb emplace_back #define all(v) v.begin(),v.end() using namespace std; using ll=long long; using pii=pair<int,int>; const int inf=1e9; int N,S,U,D,M,n; vector<pii> v[505050]; struct Mart { int t,x,m; } Q[505050]; bool cmp1(Mart a,Mart b) { if(a.t==b.t) return a.x<b.x; return a.t<b.t; } struct Seg { int T[2020202]; void update(int s,int e,int num,int key,ll val) { if(e<key||key<s) return; if(s==e) { T[num]=val; return; } int mid=(s+e)/2; update(s,mid,num*2,key,val); update(mid+1,e,num*2+1,key,val); T[num]=max(T[num*2],T[num*2+1]); } int query(int s,int e,int num,int l,int r) { if(e<l||r<s) return -inf; if(l<=s&&e<=r) return T[num]; int mid=(s+e)/2; return max(query(s,mid,num*2,l,r),query(mid+1,e,num*2+1,l,r)); } } L,R; int main() { scanf("%d%d%d%d",&N,&U,&D,&S); for(int i=1;i<=N;i++) scanf("%d%d%d",&Q[i].t,&Q[i].x,&Q[i].m); sort(Q+1,Q+N+1,cmp1); Q[0].t=0; n=S; for(int i=1;i<=N;i++) { if(Q[i].t!=Q[i-1].t) v[++M].eb(pii(Q[i].x,Q[i].m)); else v[M].eb(pii(Q[i].x,Q[i].m)); n=max(n,Q[i].x); } v[++M].eb(pii(S,0)); n+= n==S; for(int i=1;i<=4*n;i++) L.T[i]=-inf,R.T[i]=-inf; L.update(1,n,1,S,U*S); R.update(1,n,1,S,-D*S); for(int i=1;i<=M+1;i++) { int l=v[i].size(); vector<int> upres(l),downres(l); for(int j=0;j<l;j++) { auto &[x,m]=v[i][j]; int val=L.query(1,n,1,1,x); if(j==0) { if(val==-inf) upres[j]=-inf; else upres[j]=val-x*U+m; } else { if(val==-inf&&upres[j-1]==-inf) upres[j]=-inf; else upres[j]=max(upres[j-1]+(v[i][j-1].fi-x)*U,val-x*U)+m; } } for(int j=l-1;j>=0;j--) { auto &[x,m]=v[i][j]; int val=R.query(1,n,1,x,n); if(j==l-1) { if(val==-inf) downres[j]=-inf; else downres[j]=val+x*D+m; } else { if(val==-inf&&downres[j+1]==-inf) downres[j]=-inf; else downres[j]=max(downres[j+1]+(x-v[i][j+1].fi)*D,val+x*D)+m; } } for(int j=0;j<l;j++) { int val=max(upres[j],downres[j]),x=v[i][j].fi; if(val==-inf) continue; L.update(1,n,1,x,val+U*x); R.update(1,n,1,x,val-D*x); } } printf("%d",L.query(1,n,1,S,S)-U*S); }

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

salesman.cpp: In function 'int main()':
salesman.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     scanf("%d%d%d%d",&N,&U,&D,&S);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:42:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     for(int i=1;i<=N;i++) scanf("%d%d%d",&Q[i].t,&Q[i].x,&Q[i].m);
      |                           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...