Submission #415683

#	Time	Username	Problem	Language	Result	Execution time	Memory
415683		KoD	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	481 ms	199592 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 main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, D, T;
    std::cin >> N >> D >> T;
    Vec<int> A(N);
    for (auto& x : A) {
        std::cin >> x;
    }
    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