Submission #601368

#	Time	Username	Problem	Language	Result	Execution time	Memory
601368		alexander707070	The short shank; Redemption (BOI21_prison)	C++14	15 / 100	2087 ms	111344 KiB

prison

#include<bits/stdc++.h>
#define MAXN 4007
using namespace std;

const long long inf=1e16;

int n,d;
long long t,a[MAXN];
long long cost[MAXN][MAXN],mins;

long long dp[MAXN][MAXN],opt[MAXN][MAXN];

int main(){

    cin>>n>>d>>t;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }

    for(int i=1;i<=n;i++){
        mins=inf;
        for(int f=i;f<=n;f++){
            cost[i][f]=cost[i][f-1];
            if(min(a[f],f+mins)<=t)cost[i][f]++;
            mins=min(mins,a[f]-f);
        }
    }

    dp[0][0]=0;
    for(int i=1;i<=n;i++){
        dp[0][i]=dp[i][0]=inf;
    }

    for(int s=1;s<=d+1;s++){
        for(int pos=1;pos<=n;pos++){
            dp[pos][s]=inf;
            for(int k=1;k<=pos;k++){
                if(dp[k-1][s-1]+cost[k][pos]<dp[pos][s]){
                    dp[pos][s]=dp[k-1][s-1]+cost[k][pos];
                    opt[pos][s]=k;
                }
            }
        }
    }

    cout<<dp[n][d+1]<<"\n";

    return 0;
}

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