Submission #1135049

#TimeUsernameProblemLanguageResultExecution timeMemory
1135049ByeWorldSalesman (IOI09_salesman)C++20
100 / 100
732 ms40524 KiB
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<int,pii> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 5e5+30;
const int SQRT = 610;
const int MAXA = 5e5+10;
const int MOD = 1e6+7;
const int INF = 2e9+10;
const int LOG = 21;
const ld EPS = 1e-12;
void chmx(int &a, int b){ a = max(a,b); }

int n, u, d, s;

struct seg {
    int st[4*MAXN];
    void bd(int id, int l, int r){
        st[id] = -INF;
        if(l==r) return;
        bd(lf,l,md); bd(rg,md+1,r);
    }
    int que(int id, int l, int r, int x, int y){
        if(x<=l && r<=y) return st[id];
        if(r<x || y<l) return -INF;
        return max(que(lf,l,md,x,y), que(rg,md+1,r,x,y));
    }
    int upd(int id, int l,int r,int x,int p){
        if(l==r && l==x){
            chmx(st[id], p);
            return st[id];
        }
        if(r<x || x<l) return st[id];
        return st[id] = max(upd(lf,l,md,x,p), upd(rg,md+1,r,x,p));
    }
} LE, RI;

int f[MAXN], f1[MAXN], f2[MAXN], val[MAXN];
vector <pii> vec;

void calc(int l, int r){
   for(int ii=l; ii<=r; ++ii){
      int i=vec[ii].se;
      f1[i]=f2[i]=max(LE.que(1, 1, MAXA, 1, i)-d*i, RI.que(1, 1, MAXA, i, MAXA)+u*i);
   }
   f2[vec[l].se]+=val[vec[l].se];
   f1[vec[r].se]+=val[vec[r].se];
   for (int i=l+1; i<=r; ++i) f2[vec[i].se]=max(f2[vec[i].se], f2[vec[i-1].se]-d*(vec[i].se-vec[i-1].se))+val[vec[i].se];
   for (int i=r-1; i>=l; --i) f1[vec[i].se]=max(f1[vec[i].se], f1[vec[i+1].se]-u*(vec[i+1].se-vec[i].se))+val[vec[i].se];
   for (int ii=l; ii<=r; ++ii){
      int i=vec[ii].se;
      f[i]=max(f1[i], f2[i]);
      LE.upd(1, 1, MAXA, i, f[i]+d*i);
      RI.upd(1, 1, MAXA, i, f[i]-u*i);
   }
}

int32_t main(){
   cin >> n >> u >> d >> s;
   for (int i=1; i<=n; ++i){
      int t, l, m; cin >> t >> l >> m;
      vec.pb({t, l});
      val[l]=m;
   }
   vec.pb({0, s});
   vec.pb({500001, s});
   sort(vec.begin(), vec.end());
   LE.bd(1,1,MAXA); RI.bd(1,1,MAXA);
   for (int i=0; i<=MAXA; ++i) f[i]=-INF;
   f[s]=0;
   LE.upd(1, 1, MAXA, s, f[s]+d*s);
   RI.upd(1, 1, MAXA, s, f[s]-u*s);
   for (int i=1; i<(int)vec.size(); ++i){
      int j=i;
      while (j+1<(int)vec.size() && vec[j+1].fi==vec[i].fi) ++j;
      calc(i, j);
      i=j;
   }
   cout << f[s] << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...