Submission #1007542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007542		huutuan	Salesman (IOI09_salesman)	C++14	17 / 100	2431 ms	65536 KiB

salesman

#include <bits/stdc++.h>

using namespace std;

const int N=5e5+10;
const int inf=2e9;

int n, s, f[N], f1[N], f2[N], val[N], tt[N];
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]=-inf;
      for (int j=0; j<=5000; ++j){
         if (j<=i) f1[i]=max(f1[i], f[j]-d*(i-j));
         if (j>=i) f2[i]=max(f2[i], f[j]-u*(j-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]);
   }
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   int ff=0;
   cin >> n >> u >> d >> s;
   ff=max({ff, n, u, d, s});
   for (int i=1; i<=n; ++i){
      int t, l, m; cin >> t >> l >> m;
      ff=max({ff, t, l, m});
      v[t].push_back(l);
      tt[l]=t;
      val[l]=m;
      st.insert(t);
   }
   assert(ff<=5000);
   st.insert(0);
   for (int i=0; i<N; ++i) f[i]=-inf;
   f[s]=0;
   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;
}

• Subtask 1: 17 / 100