Submission #1007548

#TimeUsernameProblemLanguageResultExecution timeMemory
1007548huutuanSalesman (IOI09_salesman)C++14
5 / 100
541 ms65536 KiB
#include <bits/stdc++.h> using namespace std; const int N=5e5+10; const int inf=2e9; struct SegmentTree{ int n; vector<int> t; void init(int _n){ n=_n; t.assign(4*n+1, -inf); } void update(int k, int l, int r, int pos, int val){ if (l==r){ t[k]=val; return; } int mid=(l+r)>>1; if (pos<=mid) update(k<<1, l, mid, pos, val); else update(k<<1|1, mid+1, r, pos, val); t[k]=max(t[k<<1], t[k<<1|1]); } int get(int k, int l, int r, int L, int R){ if (r<L || R<l) return -inf; if (L<=l && r<=R) return t[k]; int mid=(l+r)>>1; return max(get(k<<1, l, mid, L, R), get(k<<1|1, mid+1, r, L, R)); } } st1, st2; int n, s, f[N], f1[N], f2[N], val[0], tt[0]; int u, d; set<int> st; vector<int> v[N]; void calc(int t){ vector<int> &vv=v[t]; sort(vv.begin(), vv.end()); for (auto &i:vv){ f1[i]=f2[i]=max(st1.get(1, 1, st1.n, 1, i)-d*i, st2.get(1, 1, st2.n, i, st2.n)+u*i); } f2[vv[0]]+=val[vv[0]]; f1[vv.back()]+=val[vv.back()]; for (int i=1; i<(int)vv.size(); ++i) f2[vv[i]]=max(f2[vv[i]], f2[vv[i-1]]-d*(vv[i]-vv[i-1]))+val[vv[i]]; for (int i=(int)vv.size()-2; i>=0; --i) f1[vv[i]]=max(f1[vv[i]], f1[vv[i+1]]-u*(vv[i+1]-vv[i]))+val[vv[i]]; for (int i:vv){ f[i]=max(f1[i], f2[i]); st1.update(1, 1, st1.n, i, f[i]+d*i); st2.update(1, 1, st2.n, i, f[i]-u*i); } } int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> u >> d >> s; for (int i=1; i<=n; ++i){ int t, l, m; cin >> t >> l >> m; v[t].push_back(l); tt[l]=t; val[l]=m; st.insert(t); } st1.init(N); st2.init(N); st.insert(0); for (int i=0; i<N; ++i) f[i]=-inf; f[s]=0; st1.update(1, 1, st1.n, s, f[s]+d*s); st2.update(1, 1, st2.n, s, f[s]-u*s); v[0].push_back(s); v[500001].push_back(s); st.insert(500001); for (auto it=next(st.begin()); it!=st.end(); ++it){ calc(*it); } cout << f[s] << '\n'; return 0; }

Compilation message (stderr)

salesman.cpp: In function 'void calc(int)':
salesman.cpp:44:24: warning: array subscript <unknown> is outside array bounds of 'int [0]' [-Warray-bounds]
   44 |    f2[vv[0]]+=val[vv[0]];
      |               ~~~~~~~~~^
salesman.cpp:33:31: note: while referencing 'val'
   33 | int n, s, f[N], f1[N], f2[N], val[0], tt[0];
      |                               ^~~
salesman.cpp:45:32: warning: array subscript <unknown> is outside array bounds of 'int [0]' [-Warray-bounds]
   45 |    f1[vv.back()]+=val[vv.back()];
      |                   ~~~~~~~~~~~~~^
salesman.cpp:33:31: note: while referencing 'val'
   33 | int n, s, f[N], f1[N], f2[N], val[0], tt[0];
      |                               ^~~
salesman.cpp:47:109: warning: array subscript <unknown> is outside array bounds of 'int [0]' [-Warray-bounds]
   47 |    for (int i=(int)vv.size()-2; i>=0; --i) f1[vv[i]]=max(f1[vv[i]], f1[vv[i+1]]-u*(vv[i+1]-vv[i]))+val[vv[i]];
      |                                                                                                    ~~~~~~~~~^
salesman.cpp:33:31: note: while referencing 'val'
   33 | int n, s, f[N], f1[N], f2[N], val[0], tt[0];
      |                               ^~~
salesman.cpp:46:106: warning: array subscript <unknown> is outside array bounds of 'int [0]' [-Warray-bounds]
   46 |    for (int i=1; i<(int)vv.size(); ++i) f2[vv[i]]=max(f2[vv[i]], f2[vv[i-1]]-d*(vv[i]-vv[i-1]))+val[vv[i]];
      |                                                                                                 ~~~~~~~~~^
salesman.cpp:33:31: note: while referencing 'val'
   33 | int n, s, f[N], f1[N], f2[N], val[0], tt[0];
      |                               ^~~
salesman.cpp: In function 'int32_t main()':
salesman.cpp:62:11: warning: array subscript <unknown> is outside array bounds of 'int [0]' [-Warray-bounds]
   62 |       tt[l]=t;
      |       ~~~~^
salesman.cpp:33:39: note: while referencing 'tt'
   33 | int n, s, f[N], f1[N], f2[N], val[0], tt[0];
      |                                       ^~
salesman.cpp:63:12: warning: array subscript <unknown> is outside array bounds of 'int [0]' [-Warray-bounds]
   63 |       val[l]=m;
      |       ~~~~~^
salesman.cpp:33:31: note: while referencing 'val'
   33 | int n, s, f[N], f1[N], f2[N], val[0], tt[0];
      |                               ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...