Submission #511314

#	Time	Username	Problem	Language	Result	Execution time	Memory
511314		600Mihnea	Salesman (IOI09_salesman)	C++17	100 / 100	1105 ms	63680 KiB

salesman

#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 (stderr)

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