#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1e9;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define f first
#define s second
pii min(pii x, pii y){
if (x.f == y.f){
return {x.f, min(x.s, y.s)};
}
if (x.f > y.f) return y;
return x;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, d, t; cin>>n>>d>>t;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++){
cin>>a[i];
}
vector<vector<int>> h(n + 1, vector<int>(n + 1));
for (int i = 1; i <= n; i++){
priority_queue<int, vector<int>, greater<int>> pq;
int tt = 0, cnt = 0;
for (int j = i; j <= n; j++){
pq.push(a[j] - tt);
int m = pq.top() + tt;
cnt += (m <= t);
h[i][j] = cnt;
tt++;
}
}
auto solve = [&](int m){
vector<ll> dp(n + 1), cnt(n + 1), l(n + 1);
dp[1] = h[1][1]; cnt[1] = 0; l[1] = 1;
for (int i = 2; i <= n; i++){
dp[i] = dp[i - 1] + (h[l[i - 1]][i] - h[l[i - 1]][i - 1]);
l[i] = l[i - 1]; cnt[i] = cnt[i - 1];
for (int j = 1; j < i; j++){
ll nw = dp[j] + h[j + 1][i] + m;
if (nw < dp[i]){
dp[i] = nw;
l[i] = j + 1;
cnt[i] = cnt[j] + 1;
}
}
}
pll ret = {dp[n], cnt[n]};
return ret;
};
int l = 0, r = inf;
while (l < r){
int m = (l + r + 1) / 2;
auto [v, k] = solve(m);
if (k >= d){
l = m;
}
else {
r = m - 1;
}
}
auto [v, k] = solve(l);
cout<<v - k * l<<"\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |