Submission #1216635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216635		maomao	The short shank; Redemption (BOI21_prison)	C++20	0 / 100	0 ms	324 KiB

prison

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define pii pair<int,int>
#define f first
#define s second

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, d, T;
    cin >> n >> d >> T;
    vector<int> t(n + 1);  
    for (int i = 1; i <= n; i++) cin >> t[i];

    vector<long long> rebel(n + 1);
    rebel[1] = t[1];

    priority_queue<pii> pq;

    for (int i = 2; i <= n; i++) {
        rebel[i] = min((long long)t[i], rebel[i - 1] + 1);
        if (rebel[i] < t[i]) {
            pq.push({t[i] - (int)(rebel[i - 1] + 1), i});
        }
    }

    vector<bool> blocked(n + 1, false);
    int used = 0;
    while (!pq.empty() && used < d) {
        int idx = pq.top().second;
        pq.pop();
        if (blocked[idx]) continue;  // alr blocked here
        blocked[idx] = true;
        rebel[idx] = t[idx];  // block propagation

        for (int i = idx + 1; i <= n; i++) {
            long long new_time = min((long long)t[i], rebel[i - 1] + 1);
            if (new_time >= rebel[i]) break; 
            rebel[i] = new_time;
            if (rebel[i] < t[i]) {
                pq.push({t[i] - (int)(rebel[i - 1] + 1), i});
            }
        }
        used++;
    }

    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (rebel[i] <= T) count++;
    }

    cout << count;
    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