Submission #426294

#	Time	Username	Problem	Language	Result	Execution time	Memory
426294		dolphingarlic	The short shank; Redemption (BOI21_prison)	C++14	0 / 100	36 ms	47264 KiB

prison

/*
Baltic 2021 The short shank; Redemption
- Call prisoners with t[i] <= T "active" and others "passive"
- We basically want to maximize the number of passive prisoners
  that don't protest
- Consider a forest where:
    - The nodes are the passive prisoners
    - The parent of node i is the first prisoner to the right of
      i that won't rebel if there's a mattress to the left of i
- We can find this forest by sweeping through the prisoners and
  using a stack
*/

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int depth[2000001], mx_child[2000001];
vector<int> children[2000001];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, d, tx;
    cin >> n >> d >> tx;

    int ans = n, mx = 0;
    priority_queue<pair<int, int>> pq;
    stack<pair<int, int>> stck;
    for (int i = 1; i <= n; i++) {
        int t;
        cin >> t;
        mx = max(mx, i + tx - t);
        if (stck.size())
            stck.top().second = max(stck.top().second, mx);
        if (t > tx) {
            if (mx < i) ans--;
            else {
                depth[i] = 1;
                while (stck.size()) {
                    int node, tmp_mx;
                    tie(node, tmp_mx) = stck.top();
                    if (tmp_mx >= i) break;
                    children[i].push_back(node);
                    if (depth[node] + 1 > depth[i]) {
                        depth[i] = depth[node] + 1;
                        mx_child[node] = i;
                    }
                    stck.pop();
                    if (stck.size())
                        stck.top().second = max(stck.top().second, tmp_mx);
                }
                mx = i + tx - t;
                stck.push({i, mx});
            }
        }
    }
    while (stck.size()) {
        int root = stck.top().first;
        pq.push({depth[root], root});
        stck.pop();
    }

    while (d-- && pq.size()) {
        pair<int, int> curr = pq.top();
        pq.pop();
        ans -= curr.first;
        int node = curr.second;
        while (node) {
            for (int i : children[node]) if (i != mx_child[node])
                pq.push({depth[i], i});
            node = mx_child[node];
        }
    }
    cout << ans;
    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