Submission #565355

#	Time	Username	Problem	Language	Result	Execution time	Memory
565355		CSQ31	The short shank; Redemption (BOI21_prison)	C++17	10 / 100	214 ms	11072 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();
		}
	}
	if(d==1){
		vector<int>s(n,0);
		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];
		int mx = 0;
		for(int i=0;i<n;i++)mx = max(mx,s[i]);
		ans-=mx;
		cout<<ans<<'\n';
		
		
	}
}

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