Submission #583527

#	Time	Username	Problem	Language	Result	Execution time	Memory
583527		WongChun1234	The short shank; Redemption (BOI21_prison)	C++14	0 / 100	227 ms	11080 KiB

prison

#include<bits/stdc++.h>
using namespace std;
const int N=2000050;
int n,d,tf,curry,t[N],pref[N],suff[N],ans=INT_MAX;
int main(){
	cin>>n>>d>>tf;
	for (int i=1;i<=n;i++){
		cin>>t[i];
	}
	curry=0;
	for (int i=1;i<=n;i++){
		pref[i]=pref[i-1];
		if (curry>=i){
			pref[i]++;
			if (t[i]<=tf) curry=max(curry,i+tf-t[i]);
		}else if (t[i]<=tf){
			pref[i]++;
			curry=i+tf-t[i];
		}
	}
	curry=n+1;
	for (int i=n;i;i--){
		suff[i]=suff[i+1];
		if (t[i]<=tf){
			suff[i]++;
			if (i+tf-t[i]<curry) suff[i]+=tf-t[i];
			else suff[i]+=curry-i-1;
			curry=i;
		}
		ans=min(ans,pref[i-1]+suff[i]);
	}
	cout<<ans<<"\n";
}

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