Submission #726957

#	Time	Username	Problem	Language	Result	Execution time	Memory
726957		gagik_2007	The short shank; Redemption (BOI21_prison)	C++17	55 / 100	2063 ms	21816 KiB

prison

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <chrono>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <functional>
#include <random>
#include <cassert>
using namespace std;

typedef long long ll;
typedef long double ld;

#define ff first
#define ss second

ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll N = 500007;
ll n, m, k;
ll a[N];
ll dp1[N], dp2[N];
ll rs[N];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		if (a[i] <= k)rs[i] = max(ll(i), min(n, i + (k - a[i])));
		else rs[i] = 0;
	}
	int j = 1;
	for (int _ = 0; _ < m; _++) {
		ll cur = 0;
		j = 1;
		for (int i = 1; i <= n; i++) {
			cur = max(cur, rs[i]);
			dp1[i] = dp1[i - 1] + (cur >= i);
		}
		stack<int>st;
		for (int i = n; i >= 1; i--) {
			dp2[i] = dp2[i + 1];
			st.push(i);
			while (!st.empty() && st.top() <= rs[i]) {
				dp2[i]++;
				st.pop();
			}
		}
		int mx = MOD;
		for (int i = 1; i <= n; i++) {
			if (dp1[i - 1] + dp2[i] < mx) {
				mx = dp1[i - 1] + dp2[i];
				j = i;
			}
			//cout << dp1[i - 1] + dp2[i] << " ";
		}
		for (int i = 1; i < j; i++) {
			rs[i] = min(rs[i], ll(j - 1));
		}
	}
	cout << dp1[j - 1] + dp2[j] << endl;
}

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