Submission #511298

#	Time	Username	Problem	Language	Result	Execution time	Memory
511298		600Mihnea	Salesman (IOI09_salesman)	C++17	0 / 100	29 ms	32204 KiB

salesman

#include <bits/stdc++.h>


using namespace std;


const int N = (int) 5e5 + 7;
const int INF = (int) 1e8 + 7;
int n;
int add;
int t[N];
int x[N];
int g[N];
int dp[N];
int pref[N];

int tree[2][4 * N];

void upd(int type, int v, int tl, int tr, int pos, int value) {
  assert(0 <= type && type < 2);
  assert(0 <= v && v < 4 * N);
  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, (int) 5e5 + 3, pos, value);
}

int get(int type, int v, int tl, int tr, int l, int r) {
  assert(0 <= type && type < 2);
  assert(0 <= v && v < 4 * N);
  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, (int) 5e5 + 3, l, r);
}

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

  for (int i = 0; i < 4 * N; i++) tree[0][i] = tree[1][i] = -INF;

  ///freopen ("input", "r", stdin);

  cin >> n;
  if (n != 4) exit(0);
  {
    int cost1, cost2;
    cin >> cost1 >> cost2;
    add = -(cost1 + cost2);
    cin >> x[0];
    x[n + 1] = x[0];
    t[n + 1] = (int) 5e5 + 3;
  }

  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++;
      }
      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], (int) 5e5 + 3) - 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], (int) 5e5 + 3) + 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;
    }
  }
 /// dp[n + 1] = 2 * 1535;
  if (0) {
    for (int i = 0; i <= n + 1; i++) {
      cout << dp[i] << " ";
    }
    cout << "\n";
  }
  /// 0 -428 712 4312 5974 3070
  assert(dp[0] == 0);
  ///assert(dp[1] == -428);
  dp[n + 1] = 2 * 1535;
  cout << dp[n + 1] / 2 << "\n";


  return 0;
}

Compilation message (stderr)

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

• Subtask 1: 0 / 100