#include <bits/stdc++.h>
using namespace std;
const int mxn = 100 * 1000 + 3, mxk = 103;
int dp[mxk][mxn], a[mxn];
int n, k;
template<class T> struct SparseTable { // comb(ID,b) = b
T ID = T();
function<T(const T&,const T&)> comb;
int n, k; vector<vector<T>> seg;
void init(int _n, T base, function<T(const T&,const T&)> join) {
n = _n; k = lg(n); comb = join; ID = base; seg.assign(_n + 1, vector<T> (k + 1, ID)); }
int lg(int x) { return 31 - __builtin_clz(x); } //CHECK THIS
void build() {
for(int i = 1; i <= n; i++) seg[i][0] = a[i];
for(int j = 1; j <= k; j++)
for(int i = 1; i + (1 << j) - 1 <= n; i++)
seg[i][j] = comb(seg[i][j - 1], seg[i + (1 << (j - 1))][j - 1]);
}
T query(int L, int R) {
int j = lg(R - L + 1);
return comb(seg[L][j], seg[R - (1 << j) + 1][j]);
}
};
SparseTable<int> st;
void f(int i, int l, int r, int optl, int optr) {
if(l > r)
return;
int mid = (l + r) >> 1, opt = -1;
dp[i][mid] = 1e9;
for(int m = optl; m < min(optr, mid); m++) {
int cost = st.query(m + 1, mid);
if(dp[i][mid] > dp[i - 1][m] + cost) {
dp[i][mid] = dp[i - 1][m] + cost;
opt = m;
}
}
//cout << i << ' ' << mid << ' ' << dp[i][mid] << ' ' << opt << '\n';
f(i, l, mid - 1, optl, opt + 1);
f(i, mid + 1, r, opt, optr);
}
signed main() {
std::ios::sync_with_stdio(0);
std::cout.tie(0);
std::cin.tie(0);
#ifdef saarang
freopen("/home/saarang/Documents/cp/input.txt", "r", stdin);
freopen("/home/saarang/Documents/cp/output.txt", "w", stdout);
#endif
cin >> n >> k;
for(int i = 0; i <= n; i++)
for(int j = 0; j <= k; j++)
dp[i][j] = 1e9;
dp[0][0] = 0;
for(int i = 1; i <= n; i++)
cin >> a[i];
st.init(n, 0, [&] (int x, int y) {
return max(x, y);
});
st.build();
for(int i = 1; i <= k; i++)
f(i, 1, n, 0, n);
// for(int i = 1; i <= k; i++) {
// for(int j = 1; j <= n; j++)
// cout << dp[i][j] << ' ';
// cout << '\n';
// }
cout << dp[k][n] << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
0 ms |
332 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
