제출 #916966

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
916966		NK_	The short shank; Redemption (BOI21_prison)	C++17	15 / 100	157 ms	44856 KiB

prison

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())
#define mp make_pair

template<class T> using V = vector<T>;
template<class T> using pq = priority_queue<T, vector<T>, less<T>>;

using vi = V<int>;
using pi = pair<int, int>;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, D, T; cin >> N >> D >> T;
	vi A(N); for(auto& x : A) cin >> x;

	V<vi> E(N);
	for(int i = 0; i < N; i++) {
		A[i] = max(T + 1 - A[i], 0);
		// cout << i << " => " << A[i] << endl;
		int r = i + A[i];
		if (r < N) E[r].pb(i);
	}
	// cout << endl;

	set<int> R; int ans = 0;

	vi LX, RX; 
	for(int i = 0; i < N; i++) {
		R.insert(i);
		for(auto& x : E[i]) R.erase(x);

		if (A[i] == 0) {
			if (sz(R)) {
				LX.pb(*rbegin(R));
				RX.pb(max(LX.back(), (sz(RX) ? RX.back() : -1)));
				// cout << i << " => " << LX.back() << " " << RX.back() << endl;
			} else {
				// cout << i << " => {}" << endl;
				ans++;
			}

		} 
		// else {
		// 	// cout << i << " " << A[i] << endl;
		// }
	}	

	int M = sz(LX);

	vi P, C, I, stk = {-1}; // parent, count
	for(int i = 0; i < M; i++) {
		if (i && mp(LX[i], RX[i]) == mp(LX[i-1], RX[i-1])) C.back()++;
		else {
			int u = sz(C); 
			while(stk.back() != -1 && LX[I[stk.back()]] > LX[i]) stk.pop_back();

			if (i && RX[i - 1] == RX[i]) P.back() = u;
			if (stk.back() != -1 && LX[I[stk.back()]] == LX[i]) P[stk.back()] = u;

			C.pb(1); I.pb(i); P.pb(-1); stk.pb(u);
		}
	}

	int K = sz(P);
	V<vi> chd(K); for(int i = 0; i < K; i++) {
		if (P[i] != -1) {
			chd[P[i]].pb(i);
			// cout << i << " <--> " << P[i] << endl;
		}
	}

	vi mx(K), vis(K), taken(K, 0), rem(K, 0), S(K, 0); 
	function<void(int)> dfs = [&](int u) {
		S[u] += C[u]; mx[u] = u; vis[u] = 1; 
		for(auto& v : chd[u]) {
			S[v] += S[u];
			dfs(v); 
			if (S[mx[u]] < S[mx[v]]) mx[u] = mx[v];
		}	
	};

	pq<pi> q; for(int i = 0; i < K; i++) if (P[i] == -1) {
		dfs(i); q.push(mp(S[mx[i]], mx[i]));
		// cout << i << " --> " << mx[i] << endl;
	}

	while(D && sz(q)) {
		auto [amt, u] = q.top(); q.pop();
		D--; ans += max(amt, 0); 
		// cout << "T: " << amt << " " << u << endl;

		while(u != -1) {
			taken[u] = 1;
			for(auto& v : chd[u]) if (!taken[v]) {
				P[v] = -1; rem[v] += rem[u] + S[u];
				// cout << "ROOT: " << v << " => " << mx[v] << " " << S[mx[v]] - rem[v] << endl;
				q.push(mp(S[mx[v]] - rem[v], mx[v]));
			}
			u = P[u];
		}
	}

	// cout << ans << endl;

	cout << N - ans << nl;

	exit(0-0);
}

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