Submission #651731

#	Time	Username	Problem	Language	Result	Execution time	Memory
651731		loctildore	Salesman (IOI09_salesman)	C++14	30 / 100	787 ms	65536 KiB

salesman

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define all(x) begin(x), end(x)
//#define endl '\n'
struct node {
  int l, r;
  node *lft, *rht;
  int lmax, rmax;
  node (int tl, int tr): l(tl), r(tr), lmax(INT_MIN/2), rmax(INT_MIN/2) {
    lft=rht=NULL;
    /*if (l+1==r) {
      lft=rht=NULL;
    }
    else {
      lft=new node(l,(l+r)/2);
      rht=new node((l+r)/2,r);
    }*/
  }
  void clean() {
    if (lft) {
      return;
    }
    if (l+1!=r) {
      lft=new node(l,(l+r)/2);
      rht=new node((l+r)/2,r);
    }
  }
};
node *root;
int n,u,d,s;
int t,loc,m;
map<int,vector<pair<int,int>>> mp;
vector<pair<int,int>> vctr;
void update(node *x, int p, int v) {
  if (x->r<=p||p<x->l) {
    return;
  }
  if (x->l+1==x->r) {
    x->lmax=max(x->lmax,v+x->l*d);
    x->rmax=max(x->rmax,v-x->l*u);
    return;
  }
  x->clean();
  update(x->lft,p,v);
  update(x->rht,p,v);
  x->lmax=max(x->lft->lmax,x->rht->lmax);
  x->rmax=max(x->lft->rmax,x->rht->rmax);
}
int qry(node *x, int l, int r, bool tmp) {
  if (r<=x->l||x->r<=l) {
    return INT_MIN/2;
  }
  if (l<=x->l&&x->r<=r) {
    return tmp?x->rmax:x->lmax;
  }
  x->clean();
  return max(qry(x->lft,l,r,tmp),qry(x->rht,l,r,tmp));
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  //freopen("salesman.in","r",stdin);
  //freopen("salesman.out","w",stdout);
  cin>>n>>u>>d>>s;
  root=new node(0,500069);
  update(root,s,0);
  for (int i = 0; i < n; i++) {
    cin>>t>>loc>>m;
    mp[t].push_back({loc,m});
  }
  for (auto &tmp : mp) {
    sort(all(tmp.s));
    vctr.clear();
    for (auto i : tmp.s) {
      tie(loc,m)=i;
      int tmp=qry(root,0,loc,0)-loc*d;
      tmp=max(tmp,qry(root,loc,500069,1)+loc*u);
      vctr.push_back({loc,tmp+m});
    }
    for (auto i : vctr) {
      update(root,i.f,i.s);
    }
  }
  int tmp=qry(root,0,s,0)-s*d;
  tmp=max(tmp,qry(root,s,500069,1)+s*u);
  cout<<tmp<<endl;
  return 0;
}

• Subtask 1: 30 / 100