Submission #930240

#	Time	Username	Problem	Language	Result	Execution time	Memory
930240		NeroZein	Autobahn (COI21_autobahn)	C++17	100 / 100	75 ms	23484 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) {
    if (rp[i] - lp[i] + 1 < t[i]) continue;
    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 < (int) pts.size() - 1; ++i) {
    auto [second, pay, stay] = pts[i];
    s += stay;
    p += pay; 
    int val = (s >= k ? p : 0);
    if (pts[i + 1][0] > second) {
      len.push_back({pts[i + 1][0] - second});
      rng.push_back({second, pts[i + 1][0] - 1, val});      
    }
  }
  long long ans = 0; 
  for (int rep = 0; rep < 2; ++rep) {
    //debug(len, rng);
    int r = -1;
    int curLen = 0; 
    long long curVal = 0; 
    int m = (int) rng.size(); 
    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;
        tmp += (long long) space * rng[r + 1][2];
        ans = max(ans, tmp); 
      }
      ans = max(ans, curVal);
      curLen -= len[l];
      curVal -= (long long) rng[l][2] * len[l];
    }    
    reverse(len.begin(), len.end());
    reverse(rng.begin(), rng.end());
  }
  cout << ans << '\n';
  return 0;
}

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