Submission #843324

#	Time	Username	Problem	Language	Result	Execution time	Memory
843324		asdfgrace	Salesman (IOI09_salesman)	C++17	62 / 100	317 ms	23076 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)
 */

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;
  int n, u, d, s;
  cin >> n >> u >> d >> s;
  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';
}

• Subtask 1: 62 / 100