Submission #1053672

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053672		vjudge1	The short shank; Redemption (BOI21_prison)	C++17	0 / 100	0 ms	348 KiB

prison

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#warning That's not the baby, that's my baby

#define debug(x) #x << " = " << x << '\n'
typedef long long ll;

int smart(int n, int D, int T, std::vector<int> a) {
	std::vector<int> v;
	int start = 0;
	int answer = n;
	bool atStart = true;
	for (int i = 1; i <= n; i++) {
		int x = a[i - 1];
		start = std::min(start + 1, x); 
		if (x > T) { 
			if (atStart) {
				answer--;
				continue; 
			} 
			if (start > T) {
				v.back()++;
			} else {
				v.push_back(1);
			}
			start = T + 1;
		} else {
			atStart = false;
		}
	}

	std::sort(v.begin(), v.end());
	std::reverse(v.begin(), v.end());

	for (int i = 0; i < D && i < (int) v.size(); i++) {
		answer -= v[i];
	}
	return answer;
}

int dumbDP(int n, int D, int T, std::vector<int> a) {
	std::vector<std::vector<int>> dp(n + 1, std::vector<int>(D + 1, -n));
	a.insert(a.begin(), 0);
	std::vector<int> nxtT(n + 2, n + 1), nxt(n + 1, n + 1);
	nxtT[n] = n + 1;
	for (int i = 1; i <= n; i++) {
		a[i] -= i;
	}
	for (int i = n - 1; i > 0; i--) {
		nxtT[i] = nxtT[i + 1];
		if (a[i + 1] + i + 1 > T) {
			nxtT[i] = i + 1;
		}
	}
	for (int i = 1; i <= n; i++) {
		if (a[i] + i > T) {
			int mini = a[i];
			int j = i;
			while (j > 0 && mini > T - i) {
				if (i != j) {
					nxt[j] = std::min(nxt[j], i);
				}
				j--;
				mini = std::min(mini, a[j]);
			}
		}
	}
	
	for (int i = 1; i <= n; i++) {
		if (a[i] > T) {
			dp[i][0] = std::max(dp[i][0], 1);
		}
		for (int k = 0; k <= D; k++) {
			if (k < D && nxtT[i] <= n) {		
				dp[nxtT[i]][k + 1] = std::max(dp[nxtT[i]][k + 1], 1 + dp[i][k]);
			}
			if (nxt[i] <= n) {
			  dp[nxt[i]][k] = std::max(dp[nxt[i]][k], 1 + dp[i][k]);
			}
		}
	}

	int maxi = 0;
	for (int i = 1; i <= n; i++) {
		for (int k = 0; k <= D; k++) {
			maxi = std::max(maxi, dp[i][k]);
			// if (dp[i][k] == 2) {
			// 	std::cout << " ? " << i << ' ' << k << '\n';
			// }
		}
	}
	return n - maxi;
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);
  #ifdef LOCAL
freopen("input.txt", "r", stdin);
  #endif
  
  int n, D, T;
	std::cin >> n >> D >> T;

	std::vector<int> a(n);
	for (auto &x : a) {
		std::cin >> x;
	}
	std::cout << dumbDP(n, D, T, a) << '\n';

  return 0;
}

Compilation message (stderr)

prison.cpp:5:2: warning: #warning That's not the baby, that's my baby [-Wcpp]
    5 | #warning That's not the baby, that's my baby
      |  ^~~~~~~

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