This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/// note: it's actually stove
#include<bits/stdc++.h>
#define endl '\n'
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
const int MAXN = 1e5 + 10;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
int n, k, a[MAXN];
void read()
{
cin >> n >> k;
for (int i = 1; i <= n; ++ i)
cin >> a[i];
}
vector < int > before(MAXN), dp(MAXN);
int inf = 1e9+10;
int best, best_opt, cost, cut;
void divide(int l, int r, int opt_left, int opt_right)
{
if(l > r)return;
int mid = (l + r)/2;
dp[mid] = inf;
best = inf;
best_opt = -1;
for (cut = opt_left; cut <= min(mid, opt_right); ++ cut)
{
cost = before[cut-1] + a[mid] - a[cut] + 1;
if(cost < best)
{
best = cost;
best_opt = cut;
}
}
dp[mid] = best;
divide(l, mid-1, opt_left, best_opt);
divide(mid+1, r, best_opt, opt_right);
}
void solve()
{
dp[0] = 0;
for (int i = 1; i <= n; ++ i)
dp[i] = inf;
for (int i = 1; i <= k; ++ i)
{
before = dp;
divide(1, n, 1, n);
}
cout << dp[n] << endl;
}
int main()
{
speed();
read();
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |