Submission #916876

#	Time	Username	Problem	Language	Result	Execution time	Memory
916876		NK_	The short shank; Redemption (BOI21_prison)	C++17	0 / 100	190 ms	45488 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())

template<class T> using V = vector<T>;
using vi = V<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);
	}

	set<int> R; int ans = 0;

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

		// for(auto& x : R) cout << x << " ";
		// cout << nl;

		if (A[i] == 0) {
			if (sz(R) == 0) ans++;
			else C[*rbegin(R)]++;
		}
	}

	vi opt; for(auto& x : C) opt.pb(x.second);

	sort(rbegin(opt), rend(opt));
	for(auto& x : opt) if (D) D--, ans += x;
	cout << N - ans << nl;

	exit(0-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