Submission #560600

#	Time	Username	Problem	Language	Result	Execution time	Memory
560600		Ooops_sorry	The short shank; Redemption (BOI21_prison)	C++14	35 / 100	2073 ms	86348 KiB

prison

#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define ld long double
#define ll long long

mt19937 rnd(51);

const int N = 2e6 + 10;
vector<int> g[N], used(N);
multiset<int> st;

int dfs(int v) {
    used[v] = 1;
    if (g[v].size() == 0) {
        return 1;
    }
    vector<int> arr;
    for (auto to : g[v]) {
        arr.pb(dfs(to));
    }
    sort(arr.rbegin(), arr.rend());
    for (int j = 1; j < arr.size(); j++) st.insert(arr[j]);
    return arr[0] + 1;
}

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif // LCOAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, d, T, ans = 0;
    cin >> n >> d >> T;
    vector<int> t(n), go(n, -1);
    for (int i = 0; i < n; i++) {
        cin >> t[i];
    }
    for (int i = 0; i < n; i++) {
        if (t[i] > T) {
            for (int j = i - 1; j >= 0; j--) {
                if (t[j] + (i - j) <= T) {
                    go[i] = j;
                    ans++;
                    break;
                }
            }
        } else {
            ans++;
        }
    }
    deque<pair<int,int>> q;
    for (int i = n - 1; i >= 0; i--) {
        while (q.size() > 0 && q.back().first > i) {
            q.pop_back();
        }
        if (go[i] != -1) {
            if (q.size() > 0) {
                g[q.back().second].pb(i);
            }
            q.pb({go[i], i});
        }
    }
    for (int i = n - 1; i >= 0; i--) {
        if (!used[i]) {
            int val = dfs(i);
            st.insert(val);
        }
    }
    for (int i = 0; i < d; i++) {
        if (st.size() == 0) break;
        int a = *st.rbegin();
        ans -= a;
        st.erase(st.find(a));
    }
    cout << ans << endl;
    return 0;
}

Compilation message (stderr)

prison.cpp: In function 'int dfs(int)':
prison.cpp:25:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for (int j = 1; j < arr.size(); j++) st.insert(arr[j]);
      |                     ~~^~~~~~~~~~~~

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