Submission #429624

#	Time	Username	Problem	Language	Result	Execution time	Memory
429624		mosiashvililuka	The short shank; Redemption (BOI21_prison)	C++14	0 / 100	129 ms	42376 KiB

prison

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,f[2000009],T,k;
vector <pair <int, int> > dp[500009];
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>k>>T;
	for(i=1; i<=a; i++) cin>>f[i];
	for(i=0; i<=a+1; i++){
		dp[i].resize(k+3);
		/*for(j=0; j<=k+1; j++){
			dp[i][j].resize(2);
		}*/
	}
	for(i=0; i<=a+1; i++){
		for(j=0; j<=k+1; j++){
			dp[i][j].first=a+3;dp[i][j].second=a+3;
		}
	}
	dp[0][0].first=0;dp[0][0].second=a+3;
	for(i=1; i<=a; i++){
		for(j=0; j<=k; j++){
			if(j!=0){
				dp[i][j].first=dp[i-1][j-1].first;
				if(f[i]<=T) dp[i][j].first++;
				dp[i][j].second=f[i];
			}
			zx=dp[i-1][j].first;
			if(min(f[i],dp[i-1][j].second+1)<=T) zx++;
			if(dp[i][j].first>zx){
				dp[i][j].first=zx;dp[i][j].second=min(f[i],dp[i-1][j].second+1);
			}else{
				if(dp[i][j].first==zx&&dp[i][j].second<min(f[i],dp[i-1][j].second+1)){
					dp[i][j].first=zx;dp[i][j].second=min(f[i],dp[i-1][j].second+1);
				}
			}
		}
	}
	cout<<dp[a][k].first;
	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