Submission #843906

#	Time	Username	Problem	Language	Result	Execution time	Memory
843906		asdfgrace	Salesman (IOI09_salesman)	C++17	85 / 100	328 ms	23192 KiB

salesman

#include <bits/stdc++.h>
using namespace std;
 
/*
 * 2 st
 * first one assumes you are travelling from the left (downstream - i increases)
 * second one assumes you are travelling from the right (upstream - i decreases)
 */
 
 
#define DEBUG(x) //x
#define A(x) DEBUG(assert(x))
#define PRINT(x) DEBUG(cerr << x)
#define PV(x) DEBUG(cerr << #x << " = " << x << '\n')
#define PV2(x) DEBUG(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define PAR(x) DEBUG(PRINT(#x << " = { "); for (auto y : x) PRINT(y << ' '); PRINT("}\n");)
#define PAR2(x) DEBUG(PRINT(#x << " = { "); for (auto [y, z] : x) PRINT(y << ',' << z << "  "); PRINT("}\n");)
#define PAR2D(x) DEBUG(PRINT(#x << ":\n"); for (auto arr : x) {PAR(arr);} PRINT('\n'));
 
 
const int ninf = -2e9;
 
template <class T> struct SegTree {
  T comb(T a, T b) {
    return max(a, b);
  }
  const T init = ninf;
  vector<T> st;
  int n;
  
  SegTree(int len) {
    n = len;
    st = vector<T>(n * 2, init);
  }
  
  void upd(int k, T x) {
    k += n;
    st[k] = x;
    for (k /= 2; k >= 1; k /= 2) {
      st[k] = comb(st[2 * k], st[2 * k + 1]);
    }
  }
  
  T quer(int l, int r) {
    T res = init;
    l += n; r += n;
    for (; l <= r && l > 0 && r > 0 ; l >>= 1, r >>= 1) {
      if (l & 1) res = comb(res, st[l++]);
      if (!(r & 1)) res = comb(res, st[r--]);
    }
    return res;
  }
};
 
int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  const int N = 500100, T = 5010;
  int n, u, d, s;
  cin >> n >> u >> d >> s;
  if (n > 5000) {
    vector<array<int, 3>> a(n);
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < 3; ++j) {
        cin >> a[i][j];
      }
    }
    sort(a.begin(), a.end());
    SegTree<int> l(N), r(N);
    for (int i = 0; i < N; ++i) {
      l.upd(i, ninf + d * i);
      r.upd(i, ninf - u * i);
    }
    l.upd(s, d * s);
    r.upd(s, -u * s);
    for (int i = 0; i < n; ++i) {
      int best = l.st[a[i][1] + N] - d * a[i][1];
      int mxl = a[i][2] - d * a[i][1] + l.quer(0, a[i][1]);
      int mxr = a[i][2] + u * a[i][1] + r.quer(a[i][1], N - 1);
      best = max(best, max(mxl, mxr));
      l.upd(a[i][1], best + d * a[i][1]);
      r.upd(a[i][1], best - u * a[i][1]);
    }
    int ans = 0;
    for (int i = 0; i < N; ++i) {
      ans = max(ans, l.st[i + N] - d * i - (i < s ? d * (s - i) : u * (i - s)));
    }
    cout << ans << '\n';
  } else {
    vector<array<int, 2>> at[T];
    for (int i = 0; i < n; ++i) {
      int t, x, p;
      cin >> t >> x >> p;
      at[t].push_back({x, p});
    }
    vector<int> l(T), r(T), sum(T), pmn(T), smx(T);
    vector<int> cur(T, ninf), next(T, ninf);
    cur[s] = next[s] = 0;
    for (int t = 0; t < T; ++t) {
      if (!at[t].size()) continue;
      fill(l.begin(), l.end(), -d);
      fill(r.begin(), r.end(), -u);
      fill(sum.begin(), sum.end(), -d - u);
      for (auto [x, p] : at[t]) {
        l[x] += p;
        r[x] += p;
        sum[x] += p;
      }
      for (int i = 1; i < T; ++i) {
        l[i] += l[i - 1];
        r[i] += r[i - 1];
        sum[i] += sum[i - 1];
      }
      pmn[0] = sum[0];
      for (int i = 1; i < T; ++i) {
        int val = sum[i];
        if (sum[i - 1] - sum[i] != d + u) {
          val = sum[i - 1] - d - u;
        }
        pmn[i] = min(pmn[i - 1], val);
      }
      smx[T - 1] = sum[T - 1];
      for (int i = T - 2; i >= 0; --i) {
        smx[i] = max(smx[i + 1], sum[i]);
      }
      if (t == 2) {
        PAR(sum); PAR(pmn);
      }
      for (int i = 1; i < T; ++i) {
        if (cur[i] == ninf) continue;
        for (auto [x, p] : at[t]) {
          int prof = 0;
          if (x > i) {
            prof = l[x] - l[i];
          } else {
            prof = r[i] - r[x];
          }
          PV(prof);
          prof += sum[min(i, x)] - pmn[min(i, x)];
          PV(sum[min(i, x)]); PV(pmn[min(i, x)]);
          PV(prof);
          prof += smx[max(i, x)] - sum[max(i, x)];
          PV(x); PV(i); PV(prof); PV(cur[i]); PRINT('\n');
          next[x] = max(next[x], cur[i] + prof);
        }
      }
      cur = next;
    }
    int ans = 0;
    for (int i = 0; i < T; ++i) {
      ans = max(ans, cur[i] - (i < s ? d * (s - i) : u * (i - s)));
    }
    cout << ans << '\n';
  }
}

• Subtask 1: 85 / 100