oj.uz

답안 #843906

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
843906 2023-09-04T16:47:14 Z asdfgrace Salesman (IOI09_salesman) C++17
85 / 100
 328 ms 23192 KB 
#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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 24 ms 600 KB Output is correct
4 Correct 97 ms 600 KB Output is correct
5 Correct 266 ms 900 KB Output is correct
6 Correct 53 ms 8792 KB Output is correct
7 Correct 69 ms 9876 KB Output is correct
8 Correct 99 ms 11336 KB Output is correct
9 Correct 124 ms 12364 KB Output is correct
10 Correct 198 ms 16500 KB Output is correct
11 Correct 208 ms 17232 KB Output is correct
12 Correct 282 ms 19188 KB Output is correct
13 Correct 274 ms 19444 KB Output is correct
14 Correct 325 ms 23192 KB Output is correct
15 Correct 299 ms 22292 KB Output is correct
16 Correct 328 ms 22160 KB Output is correct
17 Correct 0 ms 600 KB Output is correct
18 Correct 1 ms 600 KB Output is correct
19 Correct 3 ms 600 KB Output is correct
20 Correct 16 ms 600 KB Output is correct
21 Correct 36 ms 600 KB Output is correct
22 Correct 74 ms 600 KB Output is correct
23 Correct 41 ms 600 KB Output is correct
24 Correct 107 ms 592 KB Output is correct
25 Incorrect 94 ms 10836 KB Output isn't correct
26 Incorrect 147 ms 13388 KB Output isn't correct
27 Incorrect 218 ms 16980 KB Output isn't correct
28 Incorrect 232 ms 17744 KB Output isn't correct
29 Incorrect 291 ms 20560 KB Output isn't correct
30 Incorrect 307 ms 21588 KB Output isn't correct