Submission #429624

#TimeUsernameProblemLanguageResultExecution timeMemory
429624mosiashvililukaThe short shank; Redemption (BOI21_prison)C++14
0 / 100
129 ms42376 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...