Submission #866950

#	Time	Username	Problem	Language	Result	Execution time	Memory
866950		Mizo_Compiler	The short shank; Redemption (BOI21_prison)	C++17	0 / 100	132 ms	80824 KiB

prison

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
#define pb push_back
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define F first
#define S second
const int N = 2e6+5;
int n, a[N], d, t;
vector<vector<vector<ll>>> dp;

ll sol(int i, int rem, bool f) {
	if (rem < 0)return n;
	if (i == n)return 0;
	ll &ret = dp[i][rem][f];
	if (~ret)return ret;
	ret = sol(i+1, rem, (f|a[i])) + (f|a[i]);
	ret = min(ret, sol(i+1, rem-1, false) + (a[i]|f));
	return ret;
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> d >> t;
	int ans = 0;
	int cnt = 0;
	multiset<int, greater<>> s;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		a[i] = (a[i] <= t);
	}
	dp.resize(n);
	for (int i = 0; i < n; i++) {
		dp[i].resize(d+1);
		for (int j = 0; j <= d; j++) {
			dp[i][j].resize(2);
			dp[i][j][0] = dp[i][j][1] = -1;
		}
	}
	int pr[n], suf[n+1];
	suf[n] = 0;
	pr[0] = a[0];
	for (int i = 1; i < n; i++) {
		pr[i] = (pr[i-1] ? pr[i-1]+1 : pr[i-1] + a[i]);
	}
	for (int i = n-1; i >= 0; i--) {
		suf[i] = (a[i] ? n-i : suf[i+1]);
	}
	ans = pr[n-1];
	for (int i = 0; i+1 < n; i++) {
		ans = min(ans, pr[i] + suf[i+1]);
	}
	cout << ans << "\n";
}

Compilation message (stderr)

prison.cpp: In function 'int main()':
prison.cpp:29:6: warning: unused variable 'cnt' [-Wunused-variable]
   29 |  int cnt = 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