Submission #131877

#	Time	Username	Problem	Language	Result	Execution time	Memory
131877		dragonslayerit	Salesman (IOI09_salesman)	C++14	60 / 100	762 ms	65536 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 tmp[500005];

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

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:45: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:50: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: 60 / 100