Submission #565367

#	Time	Username	Problem	Language	Result	Execution time	Memory
565367		CSQ31	The short shank; Redemption (BOI21_prison)	C++17	45 / 100	2077 ms	6684 KiB

prison

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e6+1;
int a[MAXN],lf[MAXN];
int main()
{
	int n,d,t;
	cin>>n>>d>>t;
	for(int i=0;i<n;i++){
		cin>>a[i];
		lf[i] = -1;
	}
	int ans = 0;
	stack<int>stk;
	for(int i=0;i<n;i++){
		if(a[i]<=t){
			ans++;
			while(!stk.empty() && a[stk.top()] >= a[i])stk.pop();
			stk.push(i); 
		}else{
			while(!stk.empty() && i-stk.top() > t-a[stk.top()])stk.pop();
			if(stk.empty())continue;
			ans++;
			lf[i] = stk.top();
		}
	}
	vector<int>s(n,0);
	//cout<<ans<<'\n';
	//for(int i=0;i<n;i++)cout<<lf[i]<<" ";
	//cout<<'\n';
	for(int i=0;i<n;i++){
		if(lf[i] != -1){
			s[lf[i]]++;
			s[i]--;
		}
	}
	for(int i=1;i<n;i++)s[i]+=s[i-1];
	for(int k=0;k<d;k++){
		int j = 0;
		for(int i=0;i<n;i++){
			if(s[i] > s[j])j=i;
		}
		//for(int i=0;i<n;i++)cout<<s[i]<<" ";
		//cout<<'\n';
		if(!s[j])break;
		ans-=s[j];
		for(int i=j;i<n;i++){
			if(lf[i] != -1 && lf[i]<=j){
				for(int x=lf[i];x<i;x++)s[x]--;
				lf[i] = -1;
			}
			
		}
	}
	cout<<ans<<'\n';
}

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