Submission #936156

#	Time	Username	Problem	Language	Result	Execution time	Memory
936156		shoryu386	The short shank; Redemption (BOI21_prison)	C++17	15 / 100	2045 ms	251984 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];
int cost(int l, int r){
	//optimised easily to n^2
	if (memo[l][r] != -1) return memo[l][r];
	
	int ans = 0;

	if (arr[l] <= t) ans++;
	
	int carry = arr[l] + 1;
	for (int x = l+1; x <= r; x++){
		int val = min(arr[x], carry);
		if (val <= t) ans++;
		
		carry = min(carry, arr[x]);
		carry += 1;
	}
	
	return memo[l][r] = ans;
}

main(){
	cin >> n >> d >> t;
	for (int x = 0; x < n; x++) cin >> arr[x];
	
	memset(memo, -1, sizeof(memo));
	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++){
			for (int y = 0; y < x; y++){
				dp[x][z] = min(dp[x][z], dp[y][z-1] + cost(y+1, x));
			}
		}
	}
	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