Submission #936172

#	Time	Username	Problem	Language	Result	Execution time	Memory
936172		shoryu386	The short shank; Redemption (BOI21_prison)	C++17	15 / 100	2016 ms	251832 KiB

prison

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
int n, d, t;
#define MAX 4007
 
int arr[MAX], dp[MAX][MAX];
 
int memo[MAX][MAX];
void costPrecomp(int l){;
	int ans = 0;
 
	if (arr[l] <= t) memo[l][l] = 1, ans = 1;
	else memo[l][l] = 0, ans = 0;
	
	int carry = arr[l] + 1;
	for (int x = l+1; x < n; x++){
		int val = min(arr[x], carry);
		if (val <= t) ans++;
		
		carry = min(carry, arr[x]);
		carry += 1;
		
		memo[l][x] = ans;
	}
}
 
inline int cost(int l, int r){ return memo[l][r];}
 
main(){
	cin >> n >> d >> t;
	for (int x = 0; x < n; x++) cin >> arr[x];
	for (int x = 0; x < n; x++) costPrecomp(x);
	
	memset(dp, 63, sizeof(dp));
	
	for (int x = 0; x < n; x++){
		dp[x][1] = min(dp[x][1], cost(0, x));
	}
	
	for (int z = 1; z <= n; z++){
		vector<int> test;
		for (int x = 0; x < n; x++){
			int bestLoc = -1;
			for (int y = 0; y < x; y++){
				if (dp[y][z-1] + cost(y+1, x) < dp[x][z]) dp[x][z] = dp[y][z-1] + cost(y+1, x), bestLoc = y;
			}
			
			if (bestLoc != -1) test.push_back(bestLoc);
			
		}
		
		//for (auto z : test) cout << z << ' ';
		//cout << '\n';
		
		vector<int> check = test; sort(check.begin(), check.end());
		assert(check == test);
	}
	
	cout << dp[n-1][d+1];
}

Compilation message (stderr)

prison.cpp:32:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   32 | main(){
      | ^~~~

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