Submission #843363

#	Time	Username	Problem	Language	Result	Execution time	Memory
843363		asdfgrace	Salesman (IOI09_salesman)	C++17	17 / 100	1378 ms	11312 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;

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;
  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) {
      pmn[i] = min(pmn[i - 1], sum[i]);
    }
    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 += max(sum[min(i, x)] - pmn[min(i, x)], (x < i ? p : 0));
        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';
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:25:13: warning: unused variable 'N' [-Wunused-variable]
   25 |   const int N = 500100, T = 5010;
      |             ^

• Subtask 1: 17 / 100