제출 #1202096

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1202096		IBory	The short shank; Redemption (BOI21_prison)	C++20	0 / 100	122 ms	105208 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 = {0};
	for (int next : G[cur]) {
		T.push_back(DFS(next));
		if (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[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(MAX - 1, 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 || max(P[ST1.back().first].second, 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, r2);
				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);
			}
		}
	}
	A[0] = 0;

	int ans = N;
	C.push_back(DFS(0));
	sort(C.begin(), C.end(), greater<int>());
	for (int i = 0; i < M; ++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