oj.uz

답안 #600640

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
600640 2022-07-21T06:36:46 Z MilosMilutinovic Salesman (IOI09_salesman) C++14
100 / 100
 279 ms 25776 KB 
/**
 *    author:  wxhtzdy
 *    created: 21.07.2022 07:58:49
**/
#include <bits/stdc++.h>

using namespace std;

template <typename T>
class fenwick {
  public:
  vector<T> fenw;
  int n;
  fenwick(int _n) : n(_n) {
    fenw.resize(n);
  }
  void modify(int x, T v) {
    while (x < n) {
      fenw[x] += v;
      x |= (x + 1);
    }
  }
  T get(int x) {
    T v{};
    while (x >= 0) {
      v += fenw[x];
      x = (x & (x + 1)) - 1;
    }
    return v;
  }
};
struct node {
  long long a = -1e18; // don't forget to set default value
  inline void operator += (node &other) {
    a = max(a, other.a);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, u, d, s;
  cin >> n >> u >> d >> s;
  vector<array<int, 3>> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i][0] >> a[i][1] >> a[i][2];
  }
  sort(a.begin(), a.end());
  const int MAX = (int) 5e5 + 5;
  fenwick<node> f0(MAX), f1(MAX);
  f0.modify(s, {s * d});
  f1.modify(MAX - s, {-s * u});
  vector<long long> dpL(n);
  vector<long long> dpR(n);
  vector<long long> dp(n);
  for (int i = 0; i < n; i++) {
    int ptr = i;
    while (ptr + 1 < n && a[ptr + 1][0] == a[i][0]) {
      ptr += 1;
    }
    for (int j = i; j <= ptr; j++) {
      dp[j] = max(-a[j][1] * d + f0.get(a[j][1]).a, f1.get(MAX - a[j][1]).a + a[j][1] * u);
      dpL[j] = dpR[j] = dp[j];
    }
    dpL[i] += a[i][2];
    dpR[ptr] += a[ptr][2];
    for (int j = i + 1; j <= ptr; j++) {
      dpL[j] = max(dpL[j], dpL[j - 1] - d * (a[j][1] - a[j - 1][1])) + a[j][2];
    }
    for (int j = ptr - 1; j >= i; j--) {
      dpR[j] = max(dpR[j], dpR[j + 1] - u * (a[j + 1][1] - a[j][1])) + a[j][2];
    }                    
    for (int j = i; j <= ptr; j++) {
      dp[j] = max(dpL[j], dpR[j]);
    }
    for (int j = i + 1; j <= ptr; j++) {
      dp[j] = max(dp[j], dp[j - 1] - d * (a[j][1] - a[j - 1][1]));
    }
    for (int j = ptr - 1; j >= i; j--) {
      dp[j] = max(dp[j], dp[j + 1] - u * (a[j + 1][1] - a[j][1]));
    }
    for (int j = i; j <= ptr; j++) {
      f0.modify(a[j][1], {dp[j] + a[j][1] * d});
      f1.modify(MAX - a[j][1], {dp[j] - a[j][1] * u});
    }        
    i = ptr;
  }
  cout << max(-s * d + f0.get(s).a, f1.get(MAX - s).a + s * u) << '\n';                        
  return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 8148 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 3 ms 8148 KB Output is correct
4 Correct 4 ms 8188 KB Output is correct
5 Correct 5 ms 8276 KB Output is correct
6 Correct 13 ms 8756 KB Output is correct
7 Correct 29 ms 9812 KB Output is correct
8 Correct 73 ms 11596 KB Output is correct
9 Correct 81 ms 13424 KB Output is correct
10 Correct 145 ms 18684 KB Output is correct
11 Correct 156 ms 18688 KB Output is correct
12 Correct 265 ms 22244 KB Output is correct
13 Correct 208 ms 22236 KB Output is correct
14 Correct 253 ms 25756 KB Output is correct
15 Correct 244 ms 25636 KB Output is correct
16 Correct 279 ms 25636 KB Output is correct
17 Correct 4 ms 8152 KB Output is correct
18 Correct 4 ms 8148 KB Output is correct
19 Correct 4 ms 8148 KB Output is correct
20 Correct 4 ms 8148 KB Output is correct
21 Correct 7 ms 8148 KB Output is correct
22 Correct 7 ms 8236 KB Output is correct
23 Correct 7 ms 8276 KB Output is correct
24 Correct 6 ms 8276 KB Output is correct
25 Correct 73 ms 11596 KB Output is correct
26 Correct 108 ms 15084 KB Output is correct
27 Correct 172 ms 20428 KB Output is correct
28 Correct 196 ms 20424 KB Output is correct
29 Correct 273 ms 25776 KB Output is correct
30 Correct 254 ms 25636 KB Output is correct