제출 #428290

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
428290		keko37	The short shank; Redemption (BOI21_prison)	C++14	100 / 100	1178 ms	288188 KiB

prison

#include<bits/stdc++.h>

using namespace std;

typedef long long llint;
typedef pair <int, int> pi;

const int MAXN = 2000005;

int n, k, T, cnt;
int t[MAXN], dub[MAXN];
vector <int> v[MAXN], rem[MAXN], w;
vector <pi> r;
set <int> st;

void build () {
    for (int i = 1; i <= n; i++) {
        if (t[i] <= T) {
            st.insert(i);
            int j = i + T - t[i];
            if (j + 1 <= n) rem[j + 1].push_back(i);
        }
        for (auto x : rem[i]) st.erase(x);
        if (!st.empty()) {
            int lim = *st.rbegin();
            cnt++;
            if (lim < i) {
                while (!r.empty() && lim <= r.back().first) {
                    int node = r.back().second;
                    v[i].push_back(node);
                    r.pop_back();
                }
                r.push_back({lim, i});
            }
        }
    }
    while (!r.empty()) {
        int node = r.back().second;
        v[0].push_back(node);
        r.pop_back();
    }
}

void dfs (int x) {
    int mx = 0;
    for (auto sus : v[x]) {
        dfs(sus);
        mx = max(mx, dub[sus]);
    }
    dub[x] = mx + 1;
    bool naso = 0;
    if (x == 0) naso = 1;
    for (auto sus : v[x]) {
        if (dub[sus] == mx && !naso) {
            naso = 1;
        } else {
            w.push_back(dub[sus]);
        }
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k >> T;
    for (int i = 1; i <= n; i++) {
        cin >> t[i];
    }
    build();
    dfs(0);
    sort(w.begin(), w.end());
    int sol = 0;
    while (!w.empty() && k > 0) {
        sol += w.back();
        k--;
        w.pop_back();
    }
    cout << cnt - sol;
    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