Submission #131884

#	Time	Username	Problem	Language	Result	Execution time	Memory
131884		dragonslayerit	Salesman (IOI09_salesman)	C++14	90 / 100	1041 ms	47484 KiB

salesman

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

const long long INF=1e18+7;

long long dp[500005];

struct Event{
  int x,p;
  Event(int x,int p):x(x),p(p){
  }
  bool operator<(const Event& e)const{
    return x<e.x;
  }
};

std::vector<Event> 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++){
    int T,L,M;
    scanf("%d %d %d",&T,&L,&M);
    events[T].emplace_back(L-1,M);
  }
  down.set(S,S*D);
  up.set(S,-S*U);
  std::fill(dp,dp+500005,-INF);
  for(int t=1;t<=500000;t++){
    std::sort(events[t].begin(),events[t].end());
    for(Event& e:events[t]){
      long long v=e.p+std::max(down.query(0,e.x)-e.x*D,up.query(e.x,MaxSegTree::SIZE)+e.x*U);
      down.set(e.x,v+e.x*D);
      up.set(e.x,v-e.x*U);
      dp[e.x]=std::max(dp[e.x],v);
    }
    for(Event& e:events[t]){
      down.set(e.x,-INF);
      up.set(e.x,-INF);
    }
    std::reverse(events[t].begin(),events[t].end());
    for(Event& e:events[t]){
      long long v=e.p+std::max(down.query(0,e.x)-e.x*D,up.query(e.x,MaxSegTree::SIZE)+e.x*U);
      down.set(e.x,v+e.x*D);
      up.set(e.x,v-e.x*U);
      dp[e.x]=std::max(dp[e.x],v);
    }
    for(Event& e:events[t]){
      down.set(e.x,dp[e.x]+e.x*D);
      up.set(e.x,dp[e.x]-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:48: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:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d",&T,&L,&M);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 90 / 100