제출 #1022929

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1022929		gyg	The short shank; Redemption (BOI21_prison)	C++17	35 / 100	284 ms	11504 KiB

prison

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 4e3 + 5, MAX_K = 4e3 + 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;

    // Speed up
    for (int i = 1; i <= n_keys; i++) {
        aft[i] = n_keys + 1;
        for (int j = i + 1; j <= n_keys; j++)
            if (t[key[j]] - key[j] < t[key[i]] - key[i]) { aft[i] = j; break; }
        // cout << i << ": " << aft[i] << endl; 
    }
}

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: 15 / 15
• Subtask 2: 0 / 10
• Subtask 3: 20 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20