oj.uz

Submission #511314

# Submission time Handle Problem Language Result Execution time Memory
511314 2022-01-15T14:14:18 Z 600Mihnea Salesman (IOI09_salesman) C++17
100 / 100
 1105 ms 63680 KB 
#include <bits/stdc++.h>


using namespace std;


#define int long long

const int N = (int) 5e5 + 7;
const int INF = (int) 10e9;
const int C = 524288;
int n;
int add;
int t[N];
int x[N];
int g[N];
int dp[N];
int pref[N];

int tree[2][1048576 + 7];

void upd(int type, int v, int tl, int tr, int pos, int value) {
  if (pos < tl || tr < pos) return;
  if (tl == tr) {
    tree[type][v] = max(tree[type][v], value);
  } else {
    int tm = (tl + tr) / 2;
    upd(type, 2 * v, tl, tm, pos, value);
    upd(type, 2 * v + 1, tm + 1, tr, pos, value);
    tree[type][v] = max(tree[type][2 * v], tree[type][2 * v + 1]);
  }
}

void upd(int type, int pos, int value) {
  upd(type, 1, 1, C, pos, value);
}

int get(int type, int v, int tl, int tr, int l, int r) {
  if (tr < l || r < tl) return -INF;
  if (l <= tl && tr <= r) return tree[type][v];
  int tm = (tl + tr) / 2;
  return max(get(type, 2 * v, tl, tm, l, r), get(type, 2 * v + 1, tm + 1, tr, l, r));
}

int get(int type, int l, int r) {
  return get(type, 1, 1, C, l, r);
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

  for (int i = 0; i < 1048576 + 7; i++) tree[0][i] = tree[1][i] = -INF;


  cin >> n;
  {
    int cost1, cost2;
    cin >> cost1 >> cost2;
    add = -(cost1 + cost2);
    cin >> x[0];
    x[n + 1] = x[0];
    t[n + 1] = C;
  }

  for (int i = 1; i <= n; i++) {
    cin >> t[i] >> x[i] >> g[i];
    g[i] *= 2;
  }

  vector<vector<int>> guys;
  for (int i = 0; i <= n + 1; i++) {
    guys.push_back({t[i], x[i], i});
  }
  sort(guys.begin(), guys.end());
  int current = 0;
  for (int i = 0; i < (int) guys.size(); i++) {
    current += g[guys[i][2]];
    pref[i] = current;
  }
  for (int i = 0; i <= n + 1; i++) {
    x[i] = guys[i][1];
  }
  for (int i = 1; i <= n + 1; i++) {
    dp[i] = -INF;
  }
  {
    int l = 0;
    while (l < (int) guys.size()) {
      int r = l;
      while (r + 1 < (int) guys.size() && guys[r + 1][0] == guys[r][0]) {
        r++;
      }
      if (l) {
        int the_best = -INF;
        for (int j = l; j <= r; j++) {

          int e = the_best, cur = -INF;
          the_best = max(the_best, get(0, x[j], C) - pref[j - 1] - 2 * add * x[j]);
          the_best = max(the_best, get(1, 1, x[j]) - pref[j - 1]);
          dp[j] = max(dp[j], the_best + x[j] * add + pref[j]);

        }
        the_best = -INF;
        for (int j = r; j >= l; j--) {
          the_best = max(the_best, get(0, x[j], C) + pref[j]);
          the_best = max(the_best, get(1, 1, x[j]) + 2 * x[j] * add + pref[j]);
          dp[j] = max(dp[j], the_best - x[j] * add - pref[j - 1]);
        }
      }
      for (int i = l; i <= r; i++) {
        upd(0, x[i], dp[i] + x[i] * add);
        upd(1, x[i], dp[i] - x[i] * add);
      }
      l = r + 1;
    }
  }
  cout << dp[n + 1] / 2 << "\n";


  return 0;
}

Compilation message

salesman.cpp: In function 'int main()':
salesman.cpp:97:15: warning: unused variable 'e' [-Wunused-variable]
   97 |           int e = the_best, cur = -INF;
      |               ^
salesman.cpp:97:29: warning: unused variable 'cur' [-Wunused-variable]
   97 |           int e = the_best, cur = -INF;
      |                             ^~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16716 KB Output is correct
2 Correct 8 ms 16716 KB Output is correct
3 Correct 9 ms 16808 KB Output is correct
4 Correct 11 ms 16912 KB Output is correct
5 Correct 19 ms 17228 KB Output is correct
6 Correct 51 ms 18620 KB Output is correct
7 Correct 148 ms 21380 KB Output is correct
8 Correct 239 ms 26160 KB Output is correct
9 Correct 312 ms 30820 KB Output is correct
10 Correct 606 ms 44864 KB Output is correct
11 Correct 698 ms 44880 KB Output is correct
12 Correct 879 ms 54204 KB Output is correct
13 Correct 901 ms 54204 KB Output is correct
14 Correct 1092 ms 63620 KB Output is correct
15 Correct 967 ms 63672 KB Output is correct
16 Correct 1105 ms 63580 KB Output is correct
17 Correct 10 ms 16716 KB Output is correct
18 Correct 10 ms 16744 KB Output is correct
19 Correct 9 ms 16844 KB Output is correct
20 Correct 11 ms 17040 KB Output is correct
21 Correct 11 ms 16972 KB Output is correct
22 Correct 15 ms 17228 KB Output is correct
23 Correct 19 ms 17296 KB Output is correct
24 Correct 15 ms 17200 KB Output is correct
25 Correct 189 ms 26040 KB Output is correct
26 Correct 358 ms 35488 KB Output is correct
27 Correct 690 ms 49600 KB Output is correct
28 Correct 714 ms 49620 KB Output is correct
29 Correct 951 ms 63576 KB Output is correct
30 Correct 968 ms 63680 KB Output is correct