Submission #482051

#	Time	Username	Problem	Language	Result	Execution time	Memory
482051		AboAlmanal	The short shank; Redemption (BOI21_prison)	C++14	10 / 100	2082 ms	47720 KiB

prison

#include <bits/stdc++.h>

using namespace std;

const int N = 75000 + 9;
const int INF = (int) 1e9;

int dp[N][18], n, D, T, t[N], segTree[4 * N][18], lazy[4 * N][18], pre[N];

void pushDown (int v, int l, int r, int ID) {
	segTree[v][ID] += lazy[v][ID];
	
	if (l == r) {
		lazy[v][ID] = 0;
		return;
	}
	
	lazy[2 * v][ID] += lazy[v][ID];
	lazy[2 * v + 1][ID] += lazy[v][ID];
	lazy[v][ID] = 0;
	return;
}

int getRangeMin (int v, int l, int r, int L, int R, int ID) {
	pushDown (v, l, r, ID);
	
	if (L <= l && r <= R) 
		return segTree[v][ID];
	
	if (l > R || r < L)
		return INF;
	
	int mid = (l + r) / 2;
	return min (getRangeMin (2 * v, l, mid, L, R, ID), getRangeMin (2 * v + 1, mid + 1, r, L, R, ID));
}

void updateRange (int v, int l, int r, int L, int R, int ID) {
	pushDown (v, l, r, ID);
	
	if (L <= l && r <= R) {
		lazy[v][ID]++;
		pushDown (v, l, r, ID);
		return;
	}
	
	if (l > R || r < L)
		return;
	
	int mid = (l + r) / 2;
	updateRange (2 * v, l, mid, L, R, ID);
	updateRange (2 * v + 1, mid + 1, r, L, R, ID);
	segTree[v][ID] = min (segTree[2 * v][ID], segTree[2 * v + 1][ID]);
	return;
}

void updateValue (int v, int l, int r, int idx, int val, int ID) {
	pushDown (v, l, r, ID);
	if (l == r) {
		segTree[v][ID] = val;
		return;
	}
	
	int mid = (l + r) / 2;
	if (l <= idx && idx <= mid)
		updateValue (2 * v, l, mid, idx, val, ID);
	else updateValue (2 * v + 1, mid + 1, r, idx, val, ID);
	
	segTree[v][ID] = min (segTree[2 * v][ID], segTree[2 * v + 1][ID]);
	return;
}

int main () {
	cin >> n >> D >> T;
	
	D++;
	for (int i = 1; i <= n; i++) 
		cin >> t[i];
	
	set <int> s;
	s.insert (-1);
	
	vector <int> v[n + 2];
	for (int i = 1; i <= n; i++) {
		v[min(n + 1, max(i + T - t[i] + 1, i))].push_back (i);
		s.insert (i);
		for (auto u: v[i])
			s.erase (u);
		pre[i] = *(--s.end());
		//cout << pre[i] << ' ';
	}
		
		
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= D; j++) {
			updateRange (1, 0, n, 0, pre[i] - 1, j - 1);
			
			dp[i][j] = getRangeMin (1, 0, n, 0, (j == 1) ? (0) : (i - 1), j - 1);
			
			updateValue (1, 0, n, i, dp[i][j], j);
		}

	}
	
	//int res = INF;
	//for (int i = 0; i <= n; i++)
		//res = min (res, dp[i][D]);
	
	cout << dp[n][D] << "\n";

	//cout << res << "\n";
}

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