Submission #518306

#	Time	Username	Problem	Language	Result	Execution time	Memory
518306		wenqi	The short shank; Redemption (BOI21_prison)	C++17	0 / 100	71 ms	10284 KiB

prison

#include <bits/stdc++.h>

using namespace std;

int N, D, T;

int R[2000069], U[2000069];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> D >> T;
    for (int i = 0; i < N; i++) {
        int t;
        cin >> t;

        int right = i + (T - t);
        R[i] = right;
        U[i] = t;
    }
    for (int i = 1; i < N; i++) {
        R[i] = max(R[i], R[i - 1]);
    }
    vector<int> subs;
    int last = N;
    for (int i = N - 1; i >= 0; i--) {
        if (U[i] < T) {
            subs.push_back(min(R[i] + 1, last) - i - 1);
            last = i;
        }
    }
    sort(subs.begin(), subs.end(), greater<>());
    int sum = 0;
    for (int i = 0; i < min<int>(D, subs.size()); i++) {
        sum += subs[i];
    }
    cout << N - sum << endl;
    return 0;
}

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