Submission #601369

#	Time	Username	Problem	Language	Result	Execution time	Memory
601369		alexander707070	The short shank; Redemption (BOI21_prison)	C++14	15 / 100	2083 ms	111452 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;
                }
            }
        }
    }

    for(int i=1;i<=n-1;i++){
        if(opt[i][d/2+1]>opt[i+1][d/2+1])cout<<1/0;
    }

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

    return 0;
}

Compilation message (stderr)

prison.cpp: In function 'int main()':
prison.cpp:47:49: warning: division by zero [-Wdiv-by-zero]
   47 |         if(opt[i][d/2+1]>opt[i+1][d/2+1])cout<<1/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