Submission #415691

#	Time	Username	Problem	Language	Result	Execution time	Memory
415691		KoD	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	303 ms	182552 KiB

prison

#include <bits/stdc++.h>

template <class T> using Vec = std::vector<T>;

template <class F> struct RecLambda : private F {
    explicit RecLambda(F&& f): F(std::forward<F>(f)) {}
    template <class... Args> decltype(auto) operator() (Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

int read_int() {
    char c = getchar_unlocked();
    while (c < '0' or '9' < c) {
        c = getchar_unlocked();
    }
    int x = 0;
    while ('0' <= c and c <= '9') {
        x = x * 10 + (c - '0');
        c = getchar_unlocked();
    }
    return x;
}

int main() {
    const int N = read_int();
    const int D = read_int();
    const int T = read_int();
    Vec<int> A(N);
    for (auto& x : A) {
        x = read_int();
    }
    Vec<int> match(N);
    Vec<char> done(N);
    Vec<int> stack;
    int ans = N;
    for (int i = 0; i < N; ++i) {
        if (A[i] <= T) {
            done[i] = true;
            stack.push_back(i);
        }
        else {
            while (!stack.empty()) {
                const int j = stack.back();
                if (j + (T - A[j]) >= i) break;
                stack.pop_back();
            }
            if (stack.empty()) {
                done[i] = true;
                ans -= 1;
            } else {
                match[i] = stack.back();
            }
        }
    }
    Vec<int> gain, remain;
    for (int i = 0; i < N; ++i) {
        if (!done[i]) remain.push_back(i);
    }
    const auto dfs = RecLambda([&](auto&& dfs, const int u) -> int {
        Vec<int> path;
        while (!remain.empty() and match[u] <= remain.back()) {
            const int v = remain.back();
            remain.pop_back();
            path.push_back(dfs(v));
        }
        if (path.empty()) return 1;
        std::sort(path.begin(), path.end());
        const int ret = path.back() + 1;
        path.pop_back();
        std::copy(path.begin(), path.end(), std::back_inserter(gain));
        return ret;
    });
    while (!remain.empty()) {
        const int u = remain.back();
        remain.pop_back();
        gain.push_back(dfs(u));
    }
    std::sort(gain.rbegin(), gain.rend());
    for (int i = 0; i < std::min(D, (int) gain.size()); ++i) {
        ans -= gain[i];
    }
    std::cout << ans << '\n';
    return 0;
}

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