Submission #131878

#	Time	Username	Problem	Language	Result	Execution time	Memory
131878		dragonslayerit	Salesman (IOI09_salesman)	C++14	60 / 100	900 ms	53264 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);
      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);
        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:43:12: 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:48:14: 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