Submission #869988

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

prison

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

using namespace std;

int range[N][N];
int v[N];
int dp[N][N];
int n, d, t;

int solve(int l, int r){
    if(range[l][r] != -1) return range[l][r];
    if(l > r) return 0;

    if(v[l] > t) return range[l][r] = solve(l+1,r);
    int sum = t - v[l] + 1;

    if(l+sum > r) return range[l][r] = min(r-l+1,sum);

    return range[l][r] = sum + solve(l+sum, r);
}

int32_t main(){
    cin >> n >> d >> t;
    memset(range, -1, sizeof range);

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

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

    for(int pos = 1;pos <= n;pos++){
        for(int qtd = 0;qtd <= d;qtd++){
            dp[pos][qtd] = dp[pos-1][qtd-1] + (v[pos] <= t ? 1 : 0);
            for(int i = pos-1;i >= 0;i--){
                dp[pos][qtd] = max(dp[pos][qtd], dp[i][qtd-1] + solve(i+1, pos));
            }
        }
    }

    cout << dp[n][d] << '\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