Submission #847299

#	Time	Username	Problem	Language	Result	Execution time	Memory
847299		Ahmed57	The short shank; Redemption (BOI21_prison)	C++17	0 / 100	102 ms	524288 KiB

prison

#include <bits/stdc++.h>
using namespace std;
long long dp[501][501][501];
long long n,k,T,arr[501];
long long solve(int i,int la,int rem){
    if(i==n){
        return 0;
    }
    if(dp[i][la][rem]!=-1)return dp[i][la][rem];
    if(i==0){
        return dp[i][la][rem] = solve(i+1,la,rem)+(arr[i]<=T);
    }else{
        long long c1= 1e18;
        if(rem)c1 = solve(i+1,i,rem-1)+(arr[i]<=T);
        if(arr[la]+(i-la)>=arr[i]){
            c1 = min(c1,solve(i+1,i,rem)+(arr[i]<=T));
        }else{
            c1 = min(c1,solve(i+1,la,rem)+(arr[la]+(i-la)<=T));
        }
        return dp[i][la][rem] = c1;
    }
}
int main(){
    cin>>n>>k>>T;
    for(int i = 0;i<n;i++)cin>>arr[i];
    memset(dp,-1,sizeof dp);
    cout<<solve(0,0,k)<<endl;
}

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