Submission #601371

#	Time	Username	Problem	Language	Result	Execution time	Memory
601371		alexander707070	The short shank; Redemption (BOI21_prison)	C++14	35 / 100	2079 ms	78072 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][2];

void solve(int l,int r,int optl,int optr,int k){
    if(l>r)return;

    int mid=(l+r)/2,opt=0;
    dp[mid][k%2]=inf;
    for(int i=optl;i<=min(optr,mid);i++){
        if(dp[i-1][(k-1)%2]+cost[i][mid]<dp[mid][k%2]){
            dp[mid][k%2]=dp[i-1][(k-1)%2]+cost[i][mid];
            opt=i;
        }
    }

    solve(l,mid-1,optl,opt,k);
    solve(mid+1,r,opt,optr,k);
}

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[i][0]=inf;
    }

    for(int i=1;i<=d+1;i++){
        dp[0][i%2]=inf;
        solve(1,n,1,n,i);
    }

    cout<<dp[n][(d+1)%2]<<"\n";

    return 0;
}

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