oj.uz

Submission #236001

# Submission time Handle Problem Language Result Execution time Memory
236001 2020-05-30T16:22:17 Z Haunted_Cpp Salesman (IOI09_salesman) C++17
60 / 100
 263 ms 12240 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 max_on_suffix>
struct FenwickTree {
  vector<int> bit;
  const int L;
  FenwickTree (int n) : L (n + 5) {
    bit = vector<int> (L, -1e9);
  }
  void update (int idx, int delta) {
    if (max_on_suffix) idx = L - idx;
    for (; idx < L; idx += idx & (- idx)) {
      bit[idx] = max (bit[idx], delta);
    }
  }
  int query (int idx) {
    if (max_on_suffix) idx = L - 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 (MAX_FEIRAS);
  FenwickTree <false> downstream (MAX_FEIRAS);
  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

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4224 KB Output is correct
2 Correct 6 ms 4224 KB Output is correct
3 Correct 7 ms 4352 KB Output is correct
4 Correct 7 ms 4352 KB Output is correct
5 Correct 8 ms 4352 KB Output is correct
6 Correct 17 ms 4608 KB Output is correct
7 Correct 32 ms 5120 KB Output is correct
8 Correct 62 ms 5880 KB Output is correct
9 Correct 78 ms 6576 KB Output is correct
10 Correct 151 ms 8952 KB Output is correct
11 Correct 160 ms 9128 KB Output is correct
12 Correct 202 ms 10616 KB Output is correct
13 Correct 210 ms 10616 KB Output is correct
14 Correct 263 ms 12024 KB Output is correct
15 Correct 250 ms 12240 KB Output is correct
16 Correct 256 ms 12152 KB Output is correct
17 Incorrect 7 ms 4224 KB Output isn't correct
18 Incorrect 7 ms 4224 KB Output isn't correct
19 Incorrect 7 ms 4352 KB Output isn't correct
20 Incorrect 7 ms 4352 KB Output isn't correct
21 Incorrect 8 ms 4352 KB Output isn't correct
22 Incorrect 9 ms 4352 KB Output isn't correct
23 Incorrect 9 ms 4352 KB Output isn't correct
24 Incorrect 8 ms 4352 KB Output isn't correct
25 Incorrect 49 ms 5880 KB Output isn't correct
26 Incorrect 94 ms 7348 KB Output isn't correct
27 Incorrect 155 ms 9720 KB Output isn't correct
28 Incorrect 168 ms 9876 KB Output isn't correct
29 Incorrect 228 ms 12024 KB Output isn't correct
30 Incorrect 241 ms 12024 KB Output isn't correct