oj.uz

답안 #131887

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
131887 2019-07-17T21:24:20 Z dragonslayerit Salesman (IOI09_salesman) C++14
100 / 100
 972 ms 48288 KB 
#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=1<<19;
  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

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
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 32376 KB Output is correct
2 Correct 29 ms 32376 KB Output is correct
3 Correct 30 ms 32376 KB Output is correct
4 Correct 32 ms 32376 KB Output is correct
5 Correct 35 ms 32632 KB Output is correct
6 Correct 64 ms 33016 KB Output is correct
7 Correct 126 ms 33912 KB Output is correct
8 Correct 223 ms 35576 KB Output is correct
9 Correct 320 ms 37156 KB Output is correct
10 Correct 619 ms 41816 KB Output is correct
11 Correct 602 ms 41844 KB Output is correct
12 Correct 858 ms 45048 KB Output is correct
13 Correct 787 ms 44920 KB Output is correct
14 Correct 971 ms 47992 KB Output is correct
15 Correct 910 ms 48288 KB Output is correct
16 Correct 972 ms 48184 KB Output is correct
17 Correct 30 ms 32348 KB Output is correct
18 Correct 30 ms 32376 KB Output is correct
19 Correct 30 ms 32376 KB Output is correct
20 Correct 32 ms 32376 KB Output is correct
21 Correct 32 ms 32376 KB Output is correct
22 Correct 35 ms 32476 KB Output is correct
23 Correct 35 ms 32504 KB Output is correct
24 Correct 41 ms 32504 KB Output is correct
25 Correct 170 ms 33372 KB Output is correct
26 Correct 347 ms 34552 KB Output is correct
27 Correct 563 ms 35812 KB Output is correct
28 Correct 552 ms 36464 KB Output is correct
29 Correct 722 ms 37340 KB Output is correct
30 Correct 735 ms 37484 KB Output is correct