제출 #799626

#제출 시각아이디문제언어결과실행 시간메모리
799626I_Love_EliskaM_Salesman (IOI09_salesman)C++14
100 / 100
645 ms64828 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define forn(i,n) for(int i=0;i<n;++i) #define pi pair<int,int> #define f first #define s second #define pb push_back #define all(x) x.begin(),x.end() #define vii(a,n) vector<int>a(n);forn(i,n)cin>>a[i]; const int inf=1e18; struct q { int t,p,x; }; struct sgt { vector<int> t; int sz=1; sgt(int n) { while (sz<n) sz<<=1; t.assign(2*sz-1,-inf); } void upd(int v, int l, int r, int i) { if (r-l==1) return; int m=(l+r)>>1; if (i<m) upd(2*v+1,l,m,i); else upd(2*v+2,m,r,i); t[v]=max(t[2*v+1],t[2*v+2]); } void set(int i, int x) { t[sz-1+i]=x; upd(0,0,sz,i); } int query(int v, int l, int r, int lx, int rx) { if (rx<=l || r<=lx) return -inf; if (lx<=l && r<=rx) return t[v]; int m=(l+r)>>1; int lq=query(2*v+1,l,m,lx,rx); int rq=query(2*v+2,m,r,lx,rx); return max(lq,rq); } int query(int l, int r) { return query(0,0,sz,l,r); } }; void solve() { int n,u,d,s; cin>>n>>u>>d>>s; vector<q> a(n); vector<vector<pi>> z(5e5+5); forn(i,n) { cin>>a[i].t>>a[i].p>>a[i].x; z[a[i].t].pb({a[i].p,a[i].x}); } forn(i,5e5+5) sort(all(z[i])); sgt st1(5e5+5), st2(5e5+5); st1.set(s,s*d); st2.set(s,-s*u); forn(i,5e5+5){ if (!z[i].size()) continue; sort(all(z[i])); vector<int> q(z[i].size(),-inf); vector<int> p(z[i].size(),-inf); forn(j,z[i].size()) { int pos=z[i][j].f, val=z[i][j].s; int left = st1.query(0,pos); int right = st2.query(pos,5e5+5); left -= pos*d; right += pos*u; int zzz=max(left,right); p[j]=zzz; } int m=z[i].size(); vector<int> pr(m+1,0); vector<int> dist(m,0); forn(j,m) pr[j+1]=pr[j]+z[i][j].s; forn(j,m) dist[j]=(z[i][j].f-z[i][0].f)*u; vector<int> dp(m+1,0); dp[m]=pr[m]+p[m-1]-dist[m-1]; for (int j=m-1; j; --j) dp[j]=max(dp[j+1],pr[j]+p[j-1]-dist[j-1]); forn(j,m) q[j]=max(q[j],dp[j+1]-pr[j]+dist[j]); reverse(all(z[i])); reverse(all(p)); reverse(all(q)); forn(j,m) pr[j+1]=pr[j]+z[i][j].s; forn(j,m) dist[j]=(z[i][0].f-z[i][j].f)*d; dp[m]=pr[m]+p[m-1]-dist[m-1]; for (int j=m-1; j; --j) dp[j]=max(dp[j+1],pr[j]+p[j-1]-dist[j-1]); forn(j,m) q[j]=max(q[j],dp[j+1]-pr[j]+dist[j]); reverse(all(q)); reverse(all(z[i])); forn(j,z[i].size()) { int pos=z[i][j].f; int zzz=q[j]; st1.set(pos,zzz+pos*d); st2.set(pos,zzz-pos*u); } } int left = st1.query(0,s); left -= s*d; int right = st2.query(s,5e5+5); right += s*u; int ans = max(left,right); cout<<ans<<'\n'; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); }

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

salesman.cpp: In function 'void solve()':
salesman.cpp:5:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define forn(i,n) for(int i=0;i<n;++i)
......
   71 |   forn(j,z[i].size()) {
      |        ~~~~~~~~~~~~~            
salesman.cpp:71:3: note: in expansion of macro 'forn'
   71 |   forn(j,z[i].size()) {
      |   ^~~~
salesman.cpp:72:23: warning: unused variable 'val' [-Wunused-variable]
   72 |    int pos=z[i][j].f, val=z[i][j].s;
      |                       ^~~
salesman.cpp:5:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define forn(i,n) for(int i=0;i<n;++i)
......
  103 |   forn(j,z[i].size()) {
      |        ~~~~~~~~~~~~~            
salesman.cpp:103:3: note: in expansion of macro 'forn'
  103 |   forn(j,z[i].size()) {
      |   ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...