Submission #1007548

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007548		huutuan	Salesman (IOI09_salesman)	C++14	5 / 100	541 ms	65536 KiB

salesman

#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];
      |                               ^~~

• Subtask 1: 5 / 100