| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 847315 | MinaRagy06 | The short shank; Redemption (BOI21_prison) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define md ((l + r) >> 1)
using namespace std;
typedef int64_t ll;
int n, m, t;
const int N = 75'005;
struct node {
int lazy;
array<int, 2> mn;
node() {
lazy = 0;
mn = {int(1e9), int(1e9)};
}
node(array<int, 2> _mn) {
lazy = 0;
mn = _mn;
}
friend node operator+(const node &l, const node &r) {
node ret;
ret.mn = min(l.mn, r.mn);
return ret;
}
};
node seg[1 << (__lg(N - 1) + 2)];
void process(int i, int l, int r) {
if (l != r) {
for (auto c : {i << 1, i << 1 | 1}) {
seg[c].lazy += seg[i].lazy;
}
}
seg[i].mn[0] += seg[i].lazy;
seg[i].lazy = 0;
}
void upd(int i, int l, int r, int s, int e, int v) {
process(i, l, r);
if (s <= l && r <= e) {
seg[i].lazy += v;
process(i, l, r);
return;
}
if (r < s || e < l) {
return;
}
upd(i << 1, l, md, s, e, v);
upd(i << 1 | 1, md + 1, r, s, e, v);
seg[i] = seg[i << 1] + seg[i << 1 | 1];
}
void upd2(int i, int l, int r, int x, array<int, 2> v) {
process(i, l, r);
if (l == x && x == r) {
seg[i] = v;
return;
}
if (r < x || x < l) {
return;
}
upd2(i << 1, l, md, x, v);
upd2(i << 1 | 1, md + 1, r, x, v);
}
node get(int i, int l, int r, int s, int e) {
process(i, l, r);
if (s <= l && r <= e) {
return seg[i];
}
if (r < s || e < l) {
return node();
}
return get(i << 1, l, md, s, e) + get(i << 1 | 1, md + 1, r, s, e);
}
void update(int s, int e, int v) {
if (s > e) return;
upd(1, 0, n - 1, s, e, v);
}
void update(int x, array<int, 2> v) {
if (x < 0) return;
upd2(1, 0, n - 1, x, v);
}
array<int, 2> query(int s, int e) {
return get(1, 0, n - 1, s, e).mn;
}
int a[N];
array<int, 2> dp[N];
array<int, 2> calc(int c) {
for (int i = 0; i < n; i++) {
dp[i] = {int(1e9), int(1e9)};
}
stack<int> s;
dp[n] = {0, 0};
update(n - 1, dp[n]);
s.push(n);
for (int i = n - 1; i >= 0; i--) {
/*int cur = 1e9, ctr = 0;
for (int k = i; k < n; k++) {
cur = min(cur + 1, a[k]);
ctr += (cur <= t);
dp[i] = min(dp[i], {dp[k + 1][0] + ctr, dp[k + 1][1]});
}*/
// cout << i << ": ";
while (a[i] + s.top() - i <= a[s.top()]) {
int k = s.top();
s.pop();
int eni = max(i + 1, min(s.top() - 1, t + i - a[i]));
int enk = max(i + 1, min(s.top() - 1, t + k - a[k]));
// cout << enk + 1 << ' ' << eni << '\n';
if (i + 1 <= eni && eni <= s.top - 1 && i + 1 <= enk && enk <= s.top() - 1 && enk < eni) {
for (int j = enk + 1; j <= eni; j++) {
update(j, j, j - enk);
}
update(eni + 1, n - 1, eni - enk);
}
}
// cout << '\n';
if (a[i] <= t) {
update(i, n - 1, 1);
}
s.push(i);
dp[i] = query(i, n - 1);
dp[i][0] += c, dp[i][1]++;
update(i - 1, dp[i]);
}
// for (int i = 0; i <= n; i++) {
// cout << dp[i][0] << ' ';
// }
// cout << '\n';
return {dp[0][0], dp[0][1]};
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> m >> t;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
a[n] = -1;
m++;
int l = 0, r = n;
while (l <= r) {
array<int, 2> v = calc(md);
if (v[1] <= m) {
r = md - 1;
} else {
l = md + 1;
}
}
cout << calc(l)[0] - m * l << '\n';
return 0;
}