Submission #131880

#	Time	Username	Problem	Language	Result	Execution time	Memory
131880		dragonslayerit	Salesman (IOI09_salesman)	C++14	90 / 100	1055 ms	53368 KiB

salesman

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cassert>

const long long INF=1e18+7;

int ts[500005];
int ls[500005];
int ms[500005];

long long dp[500005];

std::vector<int> events[500005];
int N;

struct MaxSegTree{
  static const int SIZE=500005;
  long long st[SIZE*2];
  MaxSegTree(){
    std::fill(st,st+SIZE*2,-INF);
  }
  void pull(int i){
    st[i]=std::max(st[i<<1],st[i<<1|1]);
  }
  void set(int i,long long v){
    for(st[i+=SIZE]=v;i>1;i>>=1){
      pull(i>>1);
    }
  }
  long long query(int a,int b){
    long long res=-INF;
    for(a+=SIZE,b+=SIZE;a<b;a>>=1,b>>=1){
      if(a&1) res=std::max(res,st[a++]);
      if(b&1) res=std::max(res,st[--b]);
    }
    return res;
  }
}up,down;

int main(){
  int U,D,S;
  scanf("%d %d %d %d",&N,&U,&D,&S);
  S--;
  for(int i=0;i<N;i++){
    scanf("%d %d %d",&ts[i],&ls[i],&ms[i]);
    ls[i]--;
  }
  for(int i=0;i<N;i++){
    events[ts[i]].push_back(i);
  }
  down.set(S,S*D);
  up.set(S,-S*U);
  for(int t=1;t<=500000;t++){
    std::sort(events[t].begin(),events[t].end(),[](int i,int j){return ls[i]<ls[j];});
    for(int e:events[t]){
      int x=ls[e];
      long long v=ms[e]+std::max(down.query(0,x)-x*D,up.query(x,MaxSegTree::SIZE)+x*U);
      down.set(x,v+x*D);
      up.set(x,v-x*U);
      dp[e]=v;
    }
    for(int e:events[t]){
      int x=ls[e];
      down.set(x,-INF);
      up.set(x,-INF);
    }
    std::reverse(events[t].begin(),events[t].end());
    for(int e:events[t]){
      int x=ls[e];
      long long v=ms[e]+std::max(down.query(0,x)-x*D,up.query(x,MaxSegTree::SIZE)+x*U);
      down.set(x,v+x*D);
      up.set(x,v-x*U);
      dp[e]=std::max(dp[e],v);
    }
    for(int e:events[t]){
      int x=ls[e];
      down.set(x,dp[e]+x*D);
      up.set(x,dp[e]-x*U);
    }
  }
  printf("%lld\n",std::max(down.query(0,S)-S*D,up.query(S,MaxSegTree::SIZE)+S*U));
  return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d",&N,&U,&D,&S);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d",&ts[i],&ls[i],&ms[i]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 90 / 100