제출 #197841

#제출 시각아이디문제언어결과실행 시간메모리
197841nikolapesic2802Salesman (IOI09_salesman)C++14
60 / 100
897 ms29688 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/rope> #define ll long long #define pb push_back #define sz(x) (int)(x).size() #define mp make_pair #define f first #define s second #define all(x) x.begin(), x.end() #define D(x) cerr << #x << " is " << (x) << "\n"; #define ld long double using namespace std; using namespace __gnu_pbds; using namespace __gnu_cxx; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key() template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; } template<class T> ostream& operator<<(ostream& os, const vector<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;} template<class T> ostream& operator<<(ostream& os, const deque<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;} template<class T> ostream& operator<<(ostream& os, const set<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;} template<class T> ostream& operator<<(ostream& os, const set<T,greater<T> >& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;} template<class T> ostream& operator<<(ostream& os, const multiset<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;} template<class T> ostream& operator<<(ostream& os, const multiset<T,greater<T> >& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;} template<class T1,class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;} const int N=5e5+5; struct fair{ int t,l,m; }; bool operator<(fair a,fair b){ if(a.t!=b.t) return a.t<b.t; if(a.l!=b.l) return a.l<b.l; return a.m<b.m; } vector<fair> f; vector<int> r(N); int n,u,d,s; int getDist(int a,int b){ if(a<b) return b*d-a*d; return a*u-b*u; } struct segTree{ vector<int> mx; segTree(){mx.resize(4*N,INT_MIN/2);} void sett(int pos,int x,int l=0,int r=N-1,int i=1){ if(l==r){ assert(l==pos); mx[i]=x; return; } int m=(l+r)>>1; if(pos<=m) sett(pos,x,l,m,2*i); else sett(pos,x,m+1,r,2*i+1); mx[i]=max(mx[2*i],mx[2*i+1]); } int get(int qs,int qe,int l=0,int r=N-1,int i=1){ if(qs>r||qe<l) return INT_MIN/2; if(qs<=l&&qe>=r) return mx[i]; int m=(l+r)>>1; int sol= max(get(qs,qe,l,m,2*i),get(qs,qe,m+1,r,2*i+1)); return sol; } }up,down; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); n=5e5; u=d=s=1; scanf("%i %i %i %i",&n,&u,&d,&s); f.resize(n+1); for(int i=1;i<=n;i++) //f[i].t=5,f[i].l=1,f[i].m=4000; scanf("%i %i %i",&f[i].t,&f[i].l,&f[i].m); sort(all(f)); f.pb({0,0,0}); for(int i=n;i>=0;i--) if(f[i].t==f[i+1].t) r[i]=r[i+1]; else r[i]=i; up.sett(s,u*s); down.sett(s,-d*s); for(int i=1;i<=n;i++){ vector<int> dp(r[i]-i+1),dp2(r[i]-i+1),dp3(r[i]-i+1); for(int j=i;j<=r[i];j++) dp[j-i]=max(up.get(1,f[j].l)-f[j].l*u,down.get(f[j].l,N-1)+f[j].l*d)+f[j].m; for(int j=i;j<=r[i];j++){ dp2[j-i]=dp[j-i]; if(j!=i) dp2[j-i]=max(dp2[j-i],dp2[j-i-1]-getDist(f[j-1].l,f[j].l)+f[j].m); } for(int j=r[i];j>=i;j--){ dp3[j-i]=dp[j-i]; if(j!=r[i]) dp3[j-i]=max(dp3[j-i],dp3[j-i+1]-getDist(f[j+1].l,f[j].l)+f[j].m); dp[j-i]=max({dp2[j-i],dp3[j-i]}); } for(int j=i;j<=r[i];j++) up.sett(f[j].l,dp[j-i]+u*f[j].l),down.sett(f[j].l,dp[j-i]-d*f[j].l); i=r[i]; } int sol=max(up.get(1,s)-s*u,down.get(s,N-1)+s*d); sol=max(sol,0); printf("%i\n",sol); return 0; }

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

salesman.cpp: In function 'int main()':
salesman.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i %i",&n,&u,&d,&s);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i %i %i",&f[i].t,&f[i].l,&f[i].m);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...