Submission #521306

#	Time	Username	Problem	Language	Result	Execution time	Memory
521306		sofapuden	The short shank; Redemption (BOI21_prison)	C++14	100 / 100	254 ms	47828 KiB

prison

#include<bits/stdc++.h>

using namespace std;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n, d, t; cin >> n >> d >> t;
	vector<int> T(n+1,0);
	for(int i = 1; i <= n; ++i)cin >> T[i];
	vector<int> st;
	vector<int> l(n+1,0), r(n+1,0);
	vector<int> ans(n+1,0), mx(n+1,0);
	int cu = 0;
	for(int i = n; i; --i){
		if(T[i] > t)continue;
		++cu;
		l[cu] = i;
		r[cu] = min(n,i+t-T[i]);
		int ls = i;
		while(1){
			if(st.size() && r[cu] >= r[st.back()]){
				int x = st.back(); st.pop_back();
				--ans[mx[cu]];
				mx[cu]+=l[x]-ls-1;
				++ans[mx[cu]];
				mx[cu] = max(mx[cu],mx[x]);
				ls = r[x];
				continue;
			}
			if(st.size())r[cu] = min(r[cu],l[st.back()]-1);
			--ans[mx[cu]];
			mx[cu]+=r[cu]-ls;
			++ans[mx[cu]];
			break;	
		}
		st.push_back(cu);
	}
	for(int i = n; i; --i){
		int x = min(d,ans[i]);
		d-=x;ans[i]-=x;
	}
	for(int i = 0; i < n; ++i)cu+=ans[i]*i;
	cout << cu << '\n';
}

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