Submission #1022969

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022969		gyg	The short shank; Redemption (BOI21_prison)	C++17	10 / 100	134 ms	11480 KiB

prison

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MAX_N = 500000 + 5, MAX_K = 1 + 5, INF = 1e9;

int n, k, m;
array<int, MAX_N> t;

array<int, MAX_N> pref, suff;
void comp() {
    int val = INF;
    for (int i = 1; i <= n; i++) {
        val = min(val + 1, t[i]);
        pref[i] = pref[i - 1] + (bool) (val <= m);
    }

    stack<array<int, 3>> levels; // width, height, sum
    int sum = 0;
    for (int i = n; i >= 1; i--) {
        int width = 1, height = t[i] - i;
        while (levels.size() && levels.top()[1] >= height) {
            width += levels.top()[0];
            sum -= levels.top()[2];
            levels.pop();
        }
        int val = max(min(width, m - t[i] + 1), 0);
        levels.push({width, height, val});
        sum += val;
        suff[i] = sum;
        // cout << i << " " << sum << endl;
    }
}

int main() {
    // freopen("prison.in", "r", stdin);
    cin >> n >> k >> m;
    for (int i = 1; i <= n; i++) cin >> t[i];

    comp();
    int ans = INF;
    for (int i = 1; i <= n + 1; i++) ans = min(ans, pref[i - 1] + suff[i]);
    cout << ans << '\n';
}

• Subtask 1: 0 / 15
• Subtask 2: 10 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20