Submission #444177

#	Time	Username	Problem	Language	Result	Execution time	Memory
444177		8e7	The short shank; Redemption (BOI21_prison)	C++17	35 / 100	152 ms	47792 KiB

prison

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <set>
#include <stack>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
void debug() {cout << endl;}
template<class T, class ... U> void debug(T a, U ... b) {cout << a << " ", debug(b ...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 5005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);
int rig[maxn], f[maxn][maxn], dp[2][maxn];
void solve(int l, int r, int ql, int qr) {
	if (l >= r) return;
	int mid = (l + r) / 2;
	int bind = mid - 1;
	for (int i = ql;i < min(qr, mid);i++) {
		int val = dp[0][i] + f[i + 1][mid];	
		//debug(i, val, dp[1][mid]);
		if (val < dp[1][mid]) {
			dp[1][mid] = val;
			bind = i;
		}
	}
	//debug(mid, bind, ql, qr);
	if (r - l > 1) {
		solve(l, mid, ql, bind + 1);
		solve(mid + 1, r, bind, qr);
	}
}
const int inf = 8e7;
int main() {
	io
	int n, k, t;
	cin >> n >> k >> t;
	for (int i = 1;i <= n;i++) {
		int ti;
		cin >> ti;
		if (ti <= t) {
			rig[i] = min(n, i + t - ti); //[i, a[i]]
		}
	}
	for (int i = 1;i <= n;i++) {
		int pref = rig[i];
		for (int j = i;j <= n;j++) {
			pref = max(pref, rig[j]);
			f[i][j] = f[i][j - 1] + (pref >= j ? 1 : 0);
		}
	}	
	for (int i = 1;i <= n;i++) dp[0][i] = f[1][i], dp[1][i] = inf;
	for (int i = 1;i <= k;i++) {
		solve(1, n + 1, 0, n + 1);	
		for (int j = 1;j <= n;j++) dp[0][j] = dp[1][j], dp[1][j] = inf;
		//pary(dp[0], dp[0] + n + 1);
	}
	cout << dp[0][n] << endl;
}
/*
5 1 42
13 37 47 11 42
  */

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