#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
prison.cpp:32:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
32 | main(){
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
76 ms |
251732 KB |
Output is correct |
2 |
Correct |
138 ms |
251740 KB |
Output is correct |
3 |
Correct |
110 ms |
251792 KB |
Output is correct |
4 |
Correct |
152 ms |
251732 KB |
Output is correct |
5 |
Correct |
192 ms |
251984 KB |
Output is correct |
6 |
Correct |
153 ms |
251728 KB |
Output is correct |
7 |
Correct |
172 ms |
251788 KB |
Output is correct |
8 |
Correct |
213 ms |
251784 KB |
Output is correct |
9 |
Correct |
166 ms |
251732 KB |
Output is correct |
10 |
Correct |
161 ms |
251788 KB |
Output is correct |
11 |
Correct |
215 ms |
251788 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
251880 KB |
Output is correct |
2 |
Runtime error |
6 ms |
604 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
76 ms |
251732 KB |
Output is correct |
2 |
Correct |
138 ms |
251740 KB |
Output is correct |
3 |
Correct |
110 ms |
251792 KB |
Output is correct |
4 |
Correct |
152 ms |
251732 KB |
Output is correct |
5 |
Correct |
192 ms |
251984 KB |
Output is correct |
6 |
Correct |
153 ms |
251728 KB |
Output is correct |
7 |
Correct |
172 ms |
251788 KB |
Output is correct |
8 |
Correct |
213 ms |
251784 KB |
Output is correct |
9 |
Correct |
166 ms |
251732 KB |
Output is correct |
10 |
Correct |
161 ms |
251788 KB |
Output is correct |
11 |
Correct |
215 ms |
251788 KB |
Output is correct |
12 |
Correct |
33 ms |
251756 KB |
Output is correct |
13 |
Correct |
107 ms |
251736 KB |
Output is correct |
14 |
Correct |
104 ms |
251728 KB |
Output is correct |
15 |
Correct |
214 ms |
251796 KB |
Output is correct |
16 |
Correct |
244 ms |
251728 KB |
Output is correct |
17 |
Correct |
161 ms |
251792 KB |
Output is correct |
18 |
Correct |
160 ms |
251668 KB |
Output is correct |
19 |
Correct |
154 ms |
251784 KB |
Output is correct |
20 |
Correct |
162 ms |
251784 KB |
Output is correct |
21 |
Correct |
196 ms |
251784 KB |
Output is correct |
22 |
Correct |
176 ms |
251784 KB |
Output is correct |
23 |
Execution timed out |
2045 ms |
251808 KB |
Time limit exceeded |
24 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
251656 KB |
Output is correct |
2 |
Runtime error |
7 ms |
604 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
76 ms |
251732 KB |
Output is correct |
2 |
Correct |
138 ms |
251740 KB |
Output is correct |
3 |
Correct |
110 ms |
251792 KB |
Output is correct |
4 |
Correct |
152 ms |
251732 KB |
Output is correct |
5 |
Correct |
192 ms |
251984 KB |
Output is correct |
6 |
Correct |
153 ms |
251728 KB |
Output is correct |
7 |
Correct |
172 ms |
251788 KB |
Output is correct |
8 |
Correct |
213 ms |
251784 KB |
Output is correct |
9 |
Correct |
166 ms |
251732 KB |
Output is correct |
10 |
Correct |
161 ms |
251788 KB |
Output is correct |
11 |
Correct |
215 ms |
251788 KB |
Output is correct |
12 |
Correct |
33 ms |
251756 KB |
Output is correct |
13 |
Correct |
107 ms |
251736 KB |
Output is correct |
14 |
Correct |
104 ms |
251728 KB |
Output is correct |
15 |
Correct |
214 ms |
251796 KB |
Output is correct |
16 |
Correct |
244 ms |
251728 KB |
Output is correct |
17 |
Correct |
161 ms |
251792 KB |
Output is correct |
18 |
Correct |
160 ms |
251668 KB |
Output is correct |
19 |
Correct |
154 ms |
251784 KB |
Output is correct |
20 |
Correct |
162 ms |
251784 KB |
Output is correct |
21 |
Correct |
196 ms |
251784 KB |
Output is correct |
22 |
Correct |
176 ms |
251784 KB |
Output is correct |
23 |
Execution timed out |
2045 ms |
251808 KB |
Time limit exceeded |
24 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
76 ms |
251732 KB |
Output is correct |
2 |
Correct |
138 ms |
251740 KB |
Output is correct |
3 |
Correct |
110 ms |
251792 KB |
Output is correct |
4 |
Correct |
152 ms |
251732 KB |
Output is correct |
5 |
Correct |
192 ms |
251984 KB |
Output is correct |
6 |
Correct |
153 ms |
251728 KB |
Output is correct |
7 |
Correct |
172 ms |
251788 KB |
Output is correct |
8 |
Correct |
213 ms |
251784 KB |
Output is correct |
9 |
Correct |
166 ms |
251732 KB |
Output is correct |
10 |
Correct |
161 ms |
251788 KB |
Output is correct |
11 |
Correct |
215 ms |
251788 KB |
Output is correct |
12 |
Correct |
36 ms |
251880 KB |
Output is correct |
13 |
Runtime error |
6 ms |
604 KB |
Execution killed with signal 11 |
14 |
Halted |
0 ms |
0 KB |
- |