Submission #866953

#	Time	Username	Problem	Language	Result	Execution time	Memory
866953		Mizo_Compiler	The short shank; Redemption (BOI21_prison)	C++17	15 / 100	210 ms	524288 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, int ls) {
	if (rem < 0)return n;
	if (i == n)return 0;
	ll &ret = dp[i][rem][ls];
	if (~ret)return ret;
	int nls = ls;
	if (a[i] < a[ls] + i - ls)nls = i;
	ret = sol(i+1, rem, nls) + (min(a[ls]+i-ls, a[i]) <= t);
	ret = min(ret, sol(i+1, rem-1, i+1) + (min(a[ls]+i-ls, a[i]) <= t));
	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];
	}
	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(n);
			for (int k = 0; k < n; k++) {
				dp[i][j][k] = -1;
			}
		}
	}
	cout << sol(0, d, 0) << "\n";
}

Compilation message (stderr)

prison.cpp: In function 'int main()':
prison.cpp:30:6: warning: unused variable 'ans' [-Wunused-variable]
   30 |  int ans = 0;
      |      ^~~
prison.cpp:31:6: warning: unused variable 'cnt' [-Wunused-variable]
   31 |  int cnt = 0;
      |      ^~~

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