제출 #69557

#제출 시각아이디문제언어결과실행 시간메모리
69557gnoorSalesman (IOI09_salesman)C++17
0 / 100
1101 ms66560 KiB
#include <cstdio> #include <algorithm> #include <vector> using namespace std; long long treeu[2000100]; long long treed[2000100]; long long xu[2000100]; long long xd[2000100]; long long u,d; void update(long long *seg,int idx,int l,int r,long long c,int k,long long val) { if (l+1==r) { seg[idx]=max(seg[idx],c*l+val); return; } int m=(l+r)>>1; if (k<m) update(seg,idx*2+1,l,m,c,k,val); else update(seg,idx*2+2,m,r,c,k,val); seg[idx]=max(seg[idx*2+1],seg[idx*2+2]); } void reset(int idx,int l,int r,int k) { if (l+1==r) { xd[idx]=-1e18; xu[idx]=-1e18; return; } int m=(l+r)>>1; if (k<m) reset(idx*2+1,l,m,k); else reset(idx*2+2,m,r,k); xd[idx]=xu[idx]=-1e18; } long long query(long long *seg,int idx,int l,int r,int ll,int rr) { if (rr<=l||ll>=r) return -1e18; if (ll<=l&&rr>=r) return seg[idx]; int m=(l+r)>>1; return max(query(seg,idx*2+1,l,m,ll,rr),query(seg,idx*2+2,m,r,ll,rr)); } struct event { int pos,cost; }; bool operator< (const event &a, const event &b) { return a.pos<b.pos; } vector<event> e[500100]; int main () { int n,s; scanf("%d%lld%lld%d",&n,&u,&d,&s); for (int i=0;i<2000100;i++) { treeu[i]=-1e18; treed[i]=-1e18; xu[i]=-1e18; xd[i]=-1e18; } int a,b,c; for (int i=0;i<n;i++) { scanf("%d%d%d",&a,&b,&c); e[a].push_back(event{b,c}); } for (int i=1;i<500005;i++) { sort(e[i].begin(),e[i].end()); } update(treeu,0,1,500005,-u,s,0); update(treed,0,1,500005,d,s,0); long long cur; for (int j=0;j<500005;j++) { vector<long long> qs(e[j].size()+1,0); for (int i=0;i<(int)e[j].size();i++) { qs[i+1]=qs[i]+e[j][i].cost; } for (int i=0;i<(int)e[j].size();i++) { cur=max(query(treeu,0,1,500005,e[j][i].pos+1,500005)+e[j][i].pos*u,query(treed,0,1,500005,1,e[j][i].pos)-e[j][i].pos*d); update(xu,0,1,500005,-u,e[j][i].pos,cur+qs[i+1]); update(xd,0,1,500005,d,e[j][i].pos,cur-qs[i]); } for (int i=0;i<(int)e[j].size();i++) { cur=max(query(xu,0,1,500005,e[j][i].pos,500005)+e[j][i].pos*u-qs[i],query(xd,0,1,500005,1,e[j][i].pos)-e[j][i].pos*d+qs[i+1]); update(treeu,0,1,500005,-u,e[j][i].pos,cur); update(treed,0,1,500005,d,e[j][i].pos,cur); } for (int i=0;i<(int)e[j].size();i++) { reset(0,1,500005,e[j][i].pos); } } long long ans=max(query(treeu,0,1,500005,s,500005)+s*u,query(treed,0,1,500005,1,s)-s*d); printf("%lld\n",ans); return 0; }

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

salesman.cpp: In function 'int main()':
salesman.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%lld%lld%d",&n,&u,&d,&s);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&a,&b,&c);
   ~~~~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...