Submission #651745

#	Time	Username	Problem	Language	Result	Execution time	Memory
651745		loctildore	Salesman (IOI09_salesman)	C++14	0 / 100	3 ms	396 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;
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));
    vector<pair<int,int>> vctr;
    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});
    }
    int l=vctr.size();
    vector<int> a(l),b(l);
    a[0]=vctr[0].s;
    for (int i = 1; i < l; i++) {
      a[i]=max(vctr[i].s,a[i-1]-(vctr[i].f-vctr[i-1].f)*d+tmp.s[i].s);
    }
    b[l-1]=vctr[l-1].s;
    for (int i = l-2; ~i; i--) {
      b[i]=max(vctr[i].s,b[i+1]-(vctr[i+1].f-vctr[i].f)*u+tmp.s[i].s);
    }
    for (int i = 0; i < l; i++) {
      update(root,vctr[i].f,max(a[i],b[i]));
    }
  }
  int tmp=qry(root,0,s,0)-s*d;
  tmp=max(tmp,qry(root,s,500069,1)+s*u);
  cout<<tmp<<endl;
  return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:64:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |   freopen("salesman.in","r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:65:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |   freopen("salesman.out","w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100