//author : FatihCihan
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
const int N = 4010;
int range[N][N];
int v[N];
int dp[N][N];
int n, d, t;
void solve(){
cin >> n >> d >> t;
memset(range, -1, sizeof range);
for(int i = 1;i <= n;i++) cin >> v[i];
for(int i = 0;i <= d;i++){
dp[0][i] = 0;
}
for(int d = 0;d <= n;d++){
for(int l = 1;l <= n;l++){
int r = l+d;
if(r > n) continue;
if(v[l] > t) {range[l][r] = (l == r ? 0 : range[l+1][r]); continue;}
int sum = t - v[l] + 1;
int con = 1;
bool piroca = false;
for(int i = l+1;i < l+sum;i++){
if(i > r) break;
if(v[i] <= v[l]+con){
range[l][r] = con + range[i][r];
piroca = true;
break;
}
con++;
}
if(piroca) continue;
range[l][r] = con + (l+sum > r ? 0 : range[l+sum][r]);
}
}
for(int pos = 1;pos <= n;pos++){
for(int qtd = 0;qtd <= d;qtd++){
dp[pos][qtd] = range[1][pos];
if(qtd == 0) continue;
for(int i = pos-1;i >= 0;i--){
dp[pos][qtd] = min(dp[pos][qtd], dp[i][qtd-1] + range[i+1][pos]);
}
}
}
cout << dp[n][d] << '\n';
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int testcase = 1;//cin >> testcase;
while(testcase--)solve();
cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
64596 KB |
Output is correct |
2 |
Correct |
16 ms |
66080 KB |
Output is correct |
3 |
Correct |
15 ms |
66140 KB |
Output is correct |
4 |
Correct |
22 ms |
66732 KB |
Output is correct |
5 |
Correct |
29 ms |
66644 KB |
Output is correct |
6 |
Correct |
17 ms |
66396 KB |
Output is correct |
7 |
Correct |
20 ms |
66636 KB |
Output is correct |
8 |
Correct |
15 ms |
66652 KB |
Output is correct |
9 |
Correct |
16 ms |
66524 KB |
Output is correct |
10 |
Correct |
22 ms |
66644 KB |
Output is correct |
11 |
Correct |
28 ms |
66640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
64600 KB |
Output is correct |
2 |
Runtime error |
106 ms |
135508 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
64596 KB |
Output is correct |
2 |
Correct |
16 ms |
66080 KB |
Output is correct |
3 |
Correct |
15 ms |
66140 KB |
Output is correct |
4 |
Correct |
22 ms |
66732 KB |
Output is correct |
5 |
Correct |
29 ms |
66644 KB |
Output is correct |
6 |
Correct |
17 ms |
66396 KB |
Output is correct |
7 |
Correct |
20 ms |
66636 KB |
Output is correct |
8 |
Correct |
15 ms |
66652 KB |
Output is correct |
9 |
Correct |
16 ms |
66524 KB |
Output is correct |
10 |
Correct |
22 ms |
66644 KB |
Output is correct |
11 |
Correct |
28 ms |
66640 KB |
Output is correct |
12 |
Correct |
13 ms |
64600 KB |
Output is correct |
13 |
Correct |
15 ms |
66140 KB |
Output is correct |
14 |
Correct |
16 ms |
66140 KB |
Output is correct |
15 |
Correct |
22 ms |
66540 KB |
Output is correct |
16 |
Correct |
29 ms |
66640 KB |
Output is correct |
17 |
Correct |
17 ms |
66392 KB |
Output is correct |
18 |
Correct |
20 ms |
66652 KB |
Output is correct |
19 |
Correct |
15 ms |
66480 KB |
Output is correct |
20 |
Correct |
17 ms |
66652 KB |
Output is correct |
21 |
Correct |
21 ms |
66640 KB |
Output is correct |
22 |
Correct |
28 ms |
66640 KB |
Output is correct |
23 |
Execution timed out |
2020 ms |
74256 KB |
Time limit exceeded |
24 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
64604 KB |
Output is correct |
2 |
Runtime error |
71 ms |
131272 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
64596 KB |
Output is correct |
2 |
Correct |
16 ms |
66080 KB |
Output is correct |
3 |
Correct |
15 ms |
66140 KB |
Output is correct |
4 |
Correct |
22 ms |
66732 KB |
Output is correct |
5 |
Correct |
29 ms |
66644 KB |
Output is correct |
6 |
Correct |
17 ms |
66396 KB |
Output is correct |
7 |
Correct |
20 ms |
66636 KB |
Output is correct |
8 |
Correct |
15 ms |
66652 KB |
Output is correct |
9 |
Correct |
16 ms |
66524 KB |
Output is correct |
10 |
Correct |
22 ms |
66644 KB |
Output is correct |
11 |
Correct |
28 ms |
66640 KB |
Output is correct |
12 |
Correct |
13 ms |
64600 KB |
Output is correct |
13 |
Correct |
15 ms |
66140 KB |
Output is correct |
14 |
Correct |
16 ms |
66140 KB |
Output is correct |
15 |
Correct |
22 ms |
66540 KB |
Output is correct |
16 |
Correct |
29 ms |
66640 KB |
Output is correct |
17 |
Correct |
17 ms |
66392 KB |
Output is correct |
18 |
Correct |
20 ms |
66652 KB |
Output is correct |
19 |
Correct |
15 ms |
66480 KB |
Output is correct |
20 |
Correct |
17 ms |
66652 KB |
Output is correct |
21 |
Correct |
21 ms |
66640 KB |
Output is correct |
22 |
Correct |
28 ms |
66640 KB |
Output is correct |
23 |
Execution timed out |
2020 ms |
74256 KB |
Time limit exceeded |
24 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
64596 KB |
Output is correct |
2 |
Correct |
16 ms |
66080 KB |
Output is correct |
3 |
Correct |
15 ms |
66140 KB |
Output is correct |
4 |
Correct |
22 ms |
66732 KB |
Output is correct |
5 |
Correct |
29 ms |
66644 KB |
Output is correct |
6 |
Correct |
17 ms |
66396 KB |
Output is correct |
7 |
Correct |
20 ms |
66636 KB |
Output is correct |
8 |
Correct |
15 ms |
66652 KB |
Output is correct |
9 |
Correct |
16 ms |
66524 KB |
Output is correct |
10 |
Correct |
22 ms |
66644 KB |
Output is correct |
11 |
Correct |
28 ms |
66640 KB |
Output is correct |
12 |
Correct |
14 ms |
64600 KB |
Output is correct |
13 |
Runtime error |
106 ms |
135508 KB |
Execution killed with signal 11 |
14 |
Halted |
0 ms |
0 KB |
- |