Submission #1022940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022940		gyg	The short shank; Redemption (BOI21_prison)	C++17	10 / 100	1988 ms	6236 KiB

prison

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MAX_N = 75000 + 5, MAX_K = 15 + 5, INF = 1e9;

int n, k, m;
array<int, MAX_N> t;

int n_keys;
array<int, MAX_N> key, aft;
void precomp() {
    for (int i = 1; i <= n; i++) 
        if (t[i] <= m) n_keys++, key[n_keys] = i;
    key[n_keys + 1] = n + 1;

    stack<pii> keys;
    for (int i = n_keys; i >= 1; i--) {
        while (keys.size() && keys.top().first >= t[key[i]] - key[i]) keys.pop();
        aft[i] = (keys.empty()) ? n_keys + 1 : keys.top().second;
        keys.push({t[key[i]] - key[i], i});
    }
}

array<array<int, MAX_K>, MAX_N> dp;
void comp() {
    for (int i = n_keys; i >= 1; i--) {
        for (int c = 0; c <= k; c++) {
            int leave = dp[aft[i]][c] + min(m - t[key[i]] + 1, key[aft[i]] - key[i]);
            int take = (c == 0) ? INF : dp[i + 1][c - 1] + 1;
            dp[i][c] = min(leave, take);
            if (c != 0) {
                for (int j = i + 1; j <= aft[i] - 1; j++)
                    dp[i][c] = min(dp[i][c], dp[j + 1][c - 1] + key[j] - key[i] + 1);
            }
            // cout << i << " " << c << ": " << dp[i][c] << endl;
        }
    }
}

int main() {
    // freopen("prison.in", "r", stdin);
    cin >> n >> k >> m;
    for (int i = 1; i <= n; i++) cin >> t[i];

    precomp();
    comp();

    int ans = dp[1][k];
    cout << ans << '\n';
}

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