Submission #398928

#	Time	Username	Problem	Language	Result	Execution time	Memory
398928		AmineWeslati	The short shank; Redemption (BOI21_prison)	C++14	10 / 100	341 ms	37416 KiB

prison

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int>vi;
#define pb push_back
#define sz(v) (int)v.size()
#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=b-1; i>=a; i--)

void ckmin(int &x, int y){x=min(x,y);}
void ckmax(int &x, int y){x=max(x,y);}

void IO() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin); 
    freopen("output.txt", "w", stdout);
#endif
}
//------------------------------------------------//

const int MX=2e6+10;
const int INF=1e9;
int N,M,T; 
vi a(MX);


int main(){
	IO();

	cin>>N>>M>>T;
	FOR(i,0,N) cin>>a[i];
	
	set<int>s;
	vi val(N+1,0);
	ROF(i,0,N){
		if(i+1<N) val[i]+=val[i+1];
		if(a[i]<=T){
			int j=i+T-a[i];
			val[i]++;
			while(sz(s) && *s.begin()<=j){
				val[i]++;
				s.erase(s.begin());
			}
		}
		else{
			s.insert(i);
		}
	}
	//FOR(i,0,N) cout << val[i] << ' '; cout << endl;

	int ans=INF,r=-1,cur=0; 
	FOR(i,0,N){
		if(a[i]<=T){
			int j=i+T-a[i];
			ckmax(r,j);
		}
		if(i<=r) cur++;

		ckmin(ans,cur+val[i+1]);
	}
	cout << ans << endl;
}

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