Submission #869954

#TimeUsernameProblemLanguageResultExecution timeMemory
869954PagodePaivaThe short shank; Redemption (BOI21_prison)C++17
0 / 100
197 ms95180 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...