Submission #467078

#	Time	Username	Problem	Language	Result	Execution time	Memory
467078		MVP_Harry	The short shank; Redemption (BOI21_prison)	C++17	0 / 100	69 ms	8680 KiB

prison

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define rep(i, m, n) for (int i = m; i <= n; i++)
#define per(i, m, n) for (int i = m; i >= n; i--)
#define sz(v) (int) v.size()
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second

const int maxn = 2e6 + 5;

int N, D, T;
int t[maxn], a[maxn];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N >> D >> T;
	rep(i, 1, N) cin >> t[i];
	a[1] = t[1];
	rep(i, 2, N) a[i] = min(t[i], a[i - 1] + 1);
	int ptr = 1, ans = 0;
	vector<int> num;
	while (ptr <= N) {
		if (t[ptr] <= T) {
			ptr++;
			continue;
		}
		int j = ptr + 1, cnt = ((a[ptr] > T) ? 1 : 0);
		while (j <= N && t[j] > T) {
			if (a[j] > T) cnt++;
			j++;
		}
		if (ptr == 1) ans += j - ptr - cnt;
		else num.push_back(j - ptr - cnt);
		ptr = j;
	}
	sort(all(num), greater<int>());
	rep(i, 0, min(D - 1, sz(num) - 1)) ans += num[i];
	rep(i, 1, N) if (a[i] > T) ans++;
	cout << N - ans << endl;
	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