제출 #600640

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
600640		MilosMilutinovic	Salesman (IOI09_salesman)	C++14	100 / 100	279 ms	25776 KiB

salesman

/**
 *    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 / 100