#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
const int mxN = (int)1e5+10;
const int LINF = (int)1e18;
int n, k, T, a[mxN];
vector<vector<int>> dp,calc;
void dnc(int l, int r, int optl, int optr, int i) {
if (l > r) return;
int mid = (l+r)/2;
pair<int,int> best = {LINF, 1};
for (int k = optl; k <= min(mid, optr); k++)
best = min(best, {dp[k-1][i]+calc[k][mid],k});
dp[mid][i+1] = best.fi;
dnc(l,mid-1,optl,best.se,i);
dnc(mid+1,r,best.se,optr,i);
}
int32_t main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> k >> T; k++;
calc.resize(n+2,vector<int>(n+2,0));
dp.resize(n+2,vector<int>(k+2,LINF));
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++){
int ans = 0, mn = a[i];
for(int j = i; j <= n; j++)
mn = min(mn+1, a[j]), ans+=(mn<=T), calc[i][j] = ans;
}
for(int i = 1; i <= n; i++) dp[i][1] = calc[1][i];
for(int i = 1; i < k; i++) dnc(1,n,1,n,i);
cout << dp[n][k];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
1620 KB |
Output is correct |
3 |
Correct |
1 ms |
1748 KB |
Output is correct |
4 |
Correct |
2 ms |
2516 KB |
Output is correct |
5 |
Correct |
4 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2260 KB |
Output is correct |
7 |
Correct |
4 ms |
2388 KB |
Output is correct |
8 |
Correct |
1 ms |
2388 KB |
Output is correct |
9 |
Correct |
2 ms |
2388 KB |
Output is correct |
10 |
Correct |
2 ms |
2516 KB |
Output is correct |
11 |
Correct |
3 ms |
2644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Runtime error |
205 ms |
524288 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
1620 KB |
Output is correct |
3 |
Correct |
1 ms |
1748 KB |
Output is correct |
4 |
Correct |
2 ms |
2516 KB |
Output is correct |
5 |
Correct |
4 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2260 KB |
Output is correct |
7 |
Correct |
4 ms |
2388 KB |
Output is correct |
8 |
Correct |
1 ms |
2388 KB |
Output is correct |
9 |
Correct |
2 ms |
2388 KB |
Output is correct |
10 |
Correct |
2 ms |
2516 KB |
Output is correct |
11 |
Correct |
3 ms |
2644 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
1620 KB |
Output is correct |
14 |
Correct |
1 ms |
1748 KB |
Output is correct |
15 |
Correct |
2 ms |
2516 KB |
Output is correct |
16 |
Correct |
3 ms |
2644 KB |
Output is correct |
17 |
Correct |
1 ms |
2260 KB |
Output is correct |
18 |
Correct |
2 ms |
2388 KB |
Output is correct |
19 |
Correct |
2 ms |
2348 KB |
Output is correct |
20 |
Correct |
2 ms |
2388 KB |
Output is correct |
21 |
Correct |
2 ms |
2516 KB |
Output is correct |
22 |
Correct |
3 ms |
2644 KB |
Output is correct |
23 |
Correct |
82 ms |
129184 KB |
Output is correct |
24 |
Correct |
107 ms |
132300 KB |
Output is correct |
25 |
Correct |
126 ms |
135460 KB |
Output is correct |
26 |
Correct |
162 ms |
138672 KB |
Output is correct |
27 |
Correct |
182 ms |
141800 KB |
Output is correct |
28 |
Correct |
75 ms |
127948 KB |
Output is correct |
29 |
Correct |
87 ms |
128316 KB |
Output is correct |
30 |
Correct |
89 ms |
129868 KB |
Output is correct |
31 |
Correct |
118 ms |
133828 KB |
Output is correct |
32 |
Correct |
121 ms |
129812 KB |
Output is correct |
33 |
Correct |
124 ms |
129876 KB |
Output is correct |
34 |
Correct |
73 ms |
127656 KB |
Output is correct |
35 |
Correct |
196 ms |
141784 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Runtime error |
187 ms |
524288 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
1620 KB |
Output is correct |
3 |
Correct |
1 ms |
1748 KB |
Output is correct |
4 |
Correct |
2 ms |
2516 KB |
Output is correct |
5 |
Correct |
4 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2260 KB |
Output is correct |
7 |
Correct |
4 ms |
2388 KB |
Output is correct |
8 |
Correct |
1 ms |
2388 KB |
Output is correct |
9 |
Correct |
2 ms |
2388 KB |
Output is correct |
10 |
Correct |
2 ms |
2516 KB |
Output is correct |
11 |
Correct |
3 ms |
2644 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
1620 KB |
Output is correct |
14 |
Correct |
1 ms |
1748 KB |
Output is correct |
15 |
Correct |
2 ms |
2516 KB |
Output is correct |
16 |
Correct |
3 ms |
2644 KB |
Output is correct |
17 |
Correct |
1 ms |
2260 KB |
Output is correct |
18 |
Correct |
2 ms |
2388 KB |
Output is correct |
19 |
Correct |
2 ms |
2348 KB |
Output is correct |
20 |
Correct |
2 ms |
2388 KB |
Output is correct |
21 |
Correct |
2 ms |
2516 KB |
Output is correct |
22 |
Correct |
3 ms |
2644 KB |
Output is correct |
23 |
Correct |
82 ms |
129184 KB |
Output is correct |
24 |
Correct |
107 ms |
132300 KB |
Output is correct |
25 |
Correct |
126 ms |
135460 KB |
Output is correct |
26 |
Correct |
162 ms |
138672 KB |
Output is correct |
27 |
Correct |
182 ms |
141800 KB |
Output is correct |
28 |
Correct |
75 ms |
127948 KB |
Output is correct |
29 |
Correct |
87 ms |
128316 KB |
Output is correct |
30 |
Correct |
89 ms |
129868 KB |
Output is correct |
31 |
Correct |
118 ms |
133828 KB |
Output is correct |
32 |
Correct |
121 ms |
129812 KB |
Output is correct |
33 |
Correct |
124 ms |
129876 KB |
Output is correct |
34 |
Correct |
73 ms |
127656 KB |
Output is correct |
35 |
Correct |
196 ms |
141784 KB |
Output is correct |
36 |
Correct |
0 ms |
212 KB |
Output is correct |
37 |
Runtime error |
187 ms |
524288 KB |
Execution killed with signal 9 |
38 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
1620 KB |
Output is correct |
3 |
Correct |
1 ms |
1748 KB |
Output is correct |
4 |
Correct |
2 ms |
2516 KB |
Output is correct |
5 |
Correct |
4 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2260 KB |
Output is correct |
7 |
Correct |
4 ms |
2388 KB |
Output is correct |
8 |
Correct |
1 ms |
2388 KB |
Output is correct |
9 |
Correct |
2 ms |
2388 KB |
Output is correct |
10 |
Correct |
2 ms |
2516 KB |
Output is correct |
11 |
Correct |
3 ms |
2644 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Runtime error |
205 ms |
524288 KB |
Execution killed with signal 9 |
14 |
Halted |
0 ms |
0 KB |
- |