Submission #930224

#	Time	Username	Problem	Language	Result	Execution time	Memory
930224		NeroZein	Autobahn (COI21_autobahn)	C++17	0 / 100	1 ms	348 KiB

autobahn

#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, k, x;
  cin >> n >> k >> x;
  vector<int> lp(n), t(n), rp(n);
  for (int i = 0; i < n; ++i) {
    cin >> lp[i] >> t[i] >> rp[i];
  }
  vector<array<int, 3>> pts;//second, pay, stay
  for (int i = 0; i < n; ++i) {
    pts.push_back({lp[i], 0, 1});
    pts.push_back({lp[i] + t[i], 1, 0});
    pts.push_back({rp[i] + 1, -1, -1});
  }
  vector<int> len;
  sort(pts.begin(), pts.end());
  vector<array<int, 3>> rng;//l, r, val
  int p = 0, s = 0;
  for (int i = 0; i < n * 3 - 1; ++i) {
    auto [second, pay, stay] = pts[i];
    s += stay;
    p += pay; 
    int val = (s >= k ? p : 0);
    len.push_back({pts[i + 1][0] - second});
    rng.push_back({second, pts[i + 1][0] - 1, val});
  }
  int r = -1;
  int curLen = 0; 
  int m = n * 3 - 1; 
  long long ans = 0; 
  long long curVal = 0; 
  for (int l = 0; l < m; ++l) {
    while (r + 1 < m && curLen + len[r + 1] <= x) {
      curLen += len[r + 1];
      curVal += (long long) len[r + 1] * rng[r + 1][2];
      r++;
    }
    if (r < l) {
      curLen = curVal = 0; 
      ans = max(ans, (long long) x * rng[l][2]);
      r = l; 
      continue;
    }
    int space = x - curLen;
    if (r + 1 < m) {
      long long tmp = curVal;
      if (rng[l][2] >= rng[r + 1][2]) {
        tmp += (long long) space * rng[r + 1][2];
        ans = max(ans, tmp); 
      } else {
        int mn = min(len[l], len[r + 1] - space);
        tmp -= (long long) mn * rng[l][2];
        tmp += (long long) (mn + space) * (rng[r + 1][2]);
        ans = max(ans, tmp); 
      }
    } else {
      ans = max(ans, curVal);
    }
    curLen -= len[l];
    curVal -= (long long) rng[l][2] * len[l];
  }
  cout << ans << '\n';
  return 0;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 50