제출 #1202122

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1202122		IBory	The short shank; Redemption (BOI21_prison)	C++20	0 / 100	129 ms	120792 KiB

prison

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int MAX = 2000007;
int X[MAX], A[MAX], L[MAX];
pii P[MAX];
vector<int> G[MAX], C;

int DFS(int cur) {
	int ret = A[cur];
	vector<int> T;
	for (int next : G[cur]) {
		// cout << cur << ' ' << next << '\n';
		T.push_back(DFS(next));
		if (!T.empty() && T[0] < T.back()) swap(T[0], T.back());
	}
	for (int i = 1; i < T.size(); ++i) C.push_back(T[i]);
	return ret + (T.empty() ? 0 : T[0]);
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, M, T, CN = 0;
	cin >> N >> M >> T;
	for (int i = 1; i <= N; ++i) {
		cin >> X[i];
		if (X[i] <= T) {
			L[i] = ++CN;
			int r = min(N, i + T - X[i]);
			P[CN] = {i, r};
		}
	}

	int TN = 0;
	P[0] = {0, MAX - 1};
	vector<pii> ST1 = {{0, 0}};
	vector<int> ST2 = {0};
	for (int i = 1; i <= N; ++i) {
		if (T < X[i]) A[ST2.back()]++;
		else {
			ST1.emplace_back(L[i], L[i]);
			ST2.push_back(++TN);
		}

		while (1 < ST1.size() && (i == N || P[ST1.back().second].second <= i)) {
			auto [l2, r2] = ST1.back(); ST1.pop_back();
			auto [l1, r1] = ST1.back(); ST1.pop_back();
			int n2 = ST2.back(); ST2.pop_back();
			int n1 = ST2.back(); ST2.pop_back();

			if (n1) {
				ST1.emplace_back(l1, (P[r1].second < P[r2].second ? r2 : r1));
				ST2.push_back(++TN);
				G[TN].push_back(n1);
				G[TN].push_back(n2);
			}
			else {
				ST1.emplace_back(0, 0);
				ST2.push_back(0);
				G[0].push_back(n2);
			}
		}

		// for (auto [l, r] : ST1) cout << l << ' ' << r << " | " ;
		// cout << '\n';
		// for (int n : ST2) cout << n << ' ';
		// cout << '\n';
		// cout << '\n';

	}
	A[0] = 0;

	// for (int i = 1; i <= CN; ++i) {
	// 	auto [l, r] = P[i];
	// 	for (int j = 1; j < l; ++j) cout << ' ';
	// 	for (int j = l; j <= r; ++j) cout << '#';
	// 	cout << '\n';
	// }

	int ans = N;
	for (int i = 1; i <= N; ++i) {
		if (X[i] <= T) break;
		ans--;
	}
	C.push_back(DFS(0));
	sort(C.begin(), C.end(), greater<int>());

	for (int i = 0; i < min(M, (int)C.size()); ++i) ans -= C[i];
	cout << ans;
	return 0;
}

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