Submission #869954

#	Time	Username	Problem	Language	Result	Execution time	Memory
869954		PagodePaiva	The short shank; Redemption (BOI21_prison)	C++17	0 / 100	197 ms	95180 KiB

prison

#include<bits/stdc++.h>
#define pii pair <int, int>
#define fr first
#define sc second
#define int long long

using namespace std;

pair <int, int> minp(pii a, pii b){
    if(a.fr < b.fr) return a;
    if(a.fr > b.fr) return b;
    if(a.sc < b.sc) return a;
    return b;
}

int32_t main(){
    int n, d, t;
    cin >> n >> d >> t;

    int v[n+1];

    for(int i = 1;i <= n;i++) cin >> v[i];

    pair <int, int> dp[n+10][d+10];

    for(int i = 0;i <= d;i++){
        dp[0][i] = {0, 1e9+7};
    }

    for(int pos = 1;pos <= n;pos++){
        for(int qtd = 0;qtd <= d;qtd++){
            dp[pos][qtd] = {dp[pos-1][qtd].fr + (min(dp[pos-1][qtd].sc, v[pos]) <= t ? 1 : 0), min(dp[pos-1][qtd].sc, v[pos]) + 1};
            if(qtd == 0) continue;
            dp[pos][qtd] = minp({dp[pos-1][qtd-1].fr + (v[pos] <= t ? 1 : 0), v[pos]+1}, dp[pos][qtd]);
            // cout << dp[pos][qtd].fr << ' ' << dp[pos][qtd].sc << ' ';
        }

        // cout << '\n';
    }

    cout << dp[n][d].fr << '\n';
    return 0;
}

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