oj.uz

Submission #930225

# Submission time Handle Problem Language Result Execution time Memory
930225 2024-02-19T05:42:15 Z NeroZein Autobahn (COI21_autobahn) C++17
0 / 100
 1 ms 348 KB 
#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; 
  debug(rng); 
  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 = max(0, 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);
    }
    debug(l, r, curLen, curVal);
    curLen -= len[l];
    curVal -= (long long) rng[l][2] * len[l];
  }
  cout << ans << '\n';
  return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 344 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 344 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 344 KB Output isn't correct
12 Halted 0 ms 0 KB -