oj.uz

답안 #236000

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
236000 2020-05-30T16:07:43 Z Haunted_Cpp Salesman (IOI09_salesman) C++17
60 / 100
 270 ms 12536 KB 
/**
 *  author: Duarte Nobrega
 *  created: 30.05.2020    
**/
 
#include <bits/stdc++.h>
using namespace std;

const int MAX_FEIRAS = 5e5 + 5;

int dp [MAX_FEIRAS];
tuple<int, int, int> feiras [MAX_FEIRAS];

template <bool invertido>
struct FenwickTree {
  vector<int> bit;
  FenwickTree () {
    bit = vector<int> (MAX_FEIRAS, -1e9);
  }
  void update (int idx, int delta) {
    if (invertido) idx = MAX_FEIRAS - idx;
    for (; idx < MAX_FEIRAS; idx += idx & (- idx)) {
      bit[idx] = max (bit[idx], delta);
    }
  }
  int query (int idx) {
    if (invertido) idx = MAX_FEIRAS - idx;
    int res = -1e9;
    for (; idx > 0; idx -= idx & (- idx)) {
      res = max (res, bit[idx]);
    }
    return res;
  }
};

int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  // Solution for 60 points
  int n_feiras, descer, subir, inicio;
  cin >> n_feiras >> subir >> descer >> inicio;
  feiras[0] = make_tuple (0, inicio, 0);
  n_feiras++;
  for (int i = 1; i < n_feiras; i++) {
    int dia, onde, lucro;
    cin >> dia >> onde >> lucro;
    feiras[i] = make_tuple(dia, onde, lucro);
  }
  sort (feiras, feiras + n_feiras, [&] ( auto primeiro, auto segundo ) {
    return get<0> (primeiro) < get<0> (segundo);
  });
  FenwickTree <true> upstream;
  FenwickTree <false> downstream;
  int mx = 0;
  upstream.update (inicio, - inicio * subir);
  downstream.update (inicio, + inicio * descer); 
  for (int i = 1; i < n_feiras; i++) { 
    int cur = get<1> (feiras[i]);
    dp[i] = -1e9;
    // Upstream
    dp[i] = max (dp[i], upstream.query (cur + 1) + cur * subir + get<2> (feiras[i]));
    // Downstream
    dp[i] = max (dp[i],  downstream.query (cur - 1) - cur * descer + get<2> (feiras[i]));
    // Update upstream
    upstream.update ( cur, dp[i] - cur * subir );
    // Update downstream
    downstream.update ( cur, dp[i] + cur * descer );
    mx = max (mx, dp[i] - (cur < inicio ? descer * (inicio - cur) : subir * (cur - inicio) ) );
  }
  cout << mx << '\n';
  return 0;
}

Subtask #1
60.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 4224 KB Output is correct
2 Correct 7 ms 4224 KB Output is correct
3 Correct 7 ms 4352 KB Output is correct
4 Correct 8 ms 4352 KB Output is correct
5 Correct 9 ms 4480 KB Output is correct
6 Correct 18 ms 4736 KB Output is correct
7 Correct 32 ms 5240 KB Output is correct
8 Correct 60 ms 6136 KB Output is correct
9 Correct 85 ms 6876 KB Output is correct
10 Correct 149 ms 9336 KB Output is correct
11 Correct 165 ms 9336 KB Output is correct
12 Correct 202 ms 10872 KB Output is correct
13 Correct 204 ms 10872 KB Output is correct
14 Correct 270 ms 12508 KB Output is correct
15 Correct 257 ms 12536 KB Output is correct
16 Correct 254 ms 12408 KB Output is correct
17 Incorrect 7 ms 4352 KB Output isn't correct
18 Incorrect 7 ms 4352 KB Output isn't correct
19 Incorrect 7 ms 4352 KB Output isn't correct
20 Incorrect 8 ms 4352 KB Output isn't correct
21 Incorrect 8 ms 4352 KB Output isn't correct
22 Incorrect 9 ms 4480 KB Output isn't correct
23 Incorrect 10 ms 4344 KB Output isn't correct
24 Incorrect 9 ms 4480 KB Output isn't correct
25 Incorrect 49 ms 6008 KB Output isn't correct
26 Incorrect 99 ms 7672 KB Output isn't correct
27 Incorrect 158 ms 9976 KB Output isn't correct
28 Incorrect 173 ms 10044 KB Output isn't correct
29 Incorrect 222 ms 12280 KB Output isn't correct
30 Incorrect 229 ms 12408 KB Output isn't correct