Submission #936155

#	Time	Username	Problem	Language	Result	Execution time	Memory
936155		shoryu386	The short shank; Redemption (BOI21_prison)	C++17	0 / 100	1 ms	2396 KiB

prison

#include <bits/stdc++.h>
using namespace std;

#define int long long

int n, d, t;
#define MAX 2000007

int arr[MAX], dp[MAX];
int cost(int l, int 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 ans;
}

main(){
	cin >> n >> d >> t;
	for (int x = 0; x < n; x++) cin >> arr[x];
	
	for (int x = 0; x < n; x++){
		dp[x] = cost(0, x);
	
		for (int y = 0; y < x; y++){
			dp[x] = min(dp[x], dp[y] + cost(y+1, x));
		}
	}
	cout << dp[n-1];
}

Compilation message (stderr)

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

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