Submission #572735

#	Time	Username	Problem	Language	Result	Execution time	Memory
572735		Cyanmond	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	1016 ms	163560 KiB

prison

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

constexpr int inf = 1000000100;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REP3(i, l, r) for (int i = (l); i < (r); ++i)
#define RVP(i, n) for (int i = (n - 1); i >= 0; --i)

#define ALL(x) (x).begin(), (x).end()
int main() {
    int N, D, T;
    cin >> N >> D >> T;
    vector<int> t(N);
    for (auto &e : t) cin >> e;

    stack<int> stk;
    vector<int> ml(N, N);
    int count_v = 0;
    REP(i, N) {
        while ((not stk.empty()) and stk.top() + (T - t[stk.top()]) < i) stk.pop();
        if (t[i] <= T) {
            ++count_v;
            while ((not stk.empty()) and t[stk.top()] + i >= t[i] + stk.top()) stk.pop();
            stk.push(i);
        } else {
            if (stk.empty()) continue;
            ++count_v;
            ml[i] = stk.top();
        }
    }
    while (not stk.empty()) stk.pop();

    vector<int> b(N, N);
    RVP(i, N) {
        if (ml[i] == N) continue;
        while ((not stk.empty()) and ml[stk.top()] >= i) stk.pop();
        if (not stk.empty())
            b[i] = stk.top();
        else
            b[i] = N + 1; // base

        while ((not stk.empty()) and ml[stk.top()] >= ml[i]) stk.pop();
        stk.push(i);
    }

    vector<vector<int>> g(N);
    REP(i, N) if (b[i] < N) g[b[i]].push_back(i);

    vector<int> madpt(N, -1), chd(N, -1);
    {
        auto dfs = [&](auto &&self, const int v) -> void {
            if (madpt[v] != -1) return;
            madpt[v] = 1;
            for (const int t : g[v]) {
                self(self, t);
                if (madpt[v] < madpt[t] + 1) {
                    madpt[v] = madpt[t] + 1;
                    chd[v] = t;
                }
            }
            return;
        };
        REP(i, N) dfs(dfs, i);
    }
    vector<pair<int, int>> vs;
    REP(i, N) if (madpt[i] != -1) vs.push_back({madpt[i], i});
    sort(ALL(vs), greater());
    vector<bool> used(N);
    int sum = 0;
    REP(i, (int)size(vs)) {
        if (used[vs[i].second]) continue;
        sum += vs[i].first;
        int now = vs[i].second;
        while (now != -1) {
            used[now] = true;
            now = chd[now];
        }
        --D;
        if (D == 0) break;
    }
    cout << count_v - sum << endl;
}

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