#include <bits/stdc++.h>
using namespace std;
class segment_tree {
public:
segment_tree(size_t s) {
n = 1;
while (n < s) n <<= 1;
t.assign(2 * n, 1e18);
}
void update(int i, int x, int v, int vl, int vr) {
if (vl == vr) {
t[v] = x;
} else {
int vm = vl + vr >> 1;
if (i <= vm)
update(i, x, v << 1, vl, vm);
else
update(i, x, v << 1 | 1, vm + 1, vr);
t[v] = min(t[v << 1], t[v << 1 | 1]);
}
}
void update(int i, int x) {
update(i, x, 1, 0, n - 1);
}
long long query(int l, int r, int v, int vl, int vr) {
if (l > vr || vl > r) return 1e18;
if (l <= vl && vr <= r) return t[v];
int vm = vl + vr >> 1;
auto q1 = query(l, r, v << 1, vl, vm);
auto q2 = query(l, r, v << 1 | 1, vm + 1, vr);
return min(q1, q2);
}
long long query(int l, int r) {
return query(l, r, 1, 0, n - 1);
}
private:
int n;
vector<long long> t;
};
class sparse_table {
public:
sparse_table(vector<int>&a) : n(a.size()) {
lg.resize(1 + n);
lg[0] = lg[1] = 0;
for (int i = 2; i <= n; i++)
lg[i] = lg[i / 2] + 1;
mx.assign(n, vector<int>(1 + lg[n]));
for (int j = 0; j <= lg[n]; j++)
for (int i = 0; i <= n - (1 << j); i++)
if (j == 0) mx[i][j] = a[i];
else mx[i][j] = max(mx[i][j-1], mx[i+(1<<(j-1))][j-1]);
}
int query(int l, int r) {
int d = lg[r-l+1];
return max(mx[l][d], mx[r-(1<<d)+1][d]);
}
private:
int n;
vector<int> lg;
vector<vector<int>> mx;
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<int> a(1 + n);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sparse_table st(a);
segment_tree str(n + 1);
vector<vector<long long>> dp(1 + n, vector<long long>(1 + k, 1e18));
for (int i = 1; i <= n; i++) {
dp[i][1] = st.query(1, i);
str.update(i, dp[i][1]);
}
int K = k;
for (int k = 2; k <= K; k++) {
for (int i = 2; i <= n; i++) {
int l = 1, r = i;
while (l < r) {
int m = (l + r) / 2;
if (st.query(m, i) == a[i])
r = m;
else
l = m + 1;
}
dp[i][k] = min(dp[i][k], dp[r - 1][k]);
if (st.query(r, i) == a[i]) {
long long mn = str.query(r - 1, i - 1);
dp[i][k] = min(dp[i][k], mn + a[i]);
}
}
for (int i = 1; i <= n; i++) {
str.update(i, dp[i][k]);
}
}
cout << dp[n][k] << '\n';
return 0;
}
Compilation message
blocks.cpp: In constructor 'segment_tree::segment_tree(size_t)':
blocks.cpp:9:12: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
9 | while (n < s) n <<= 1;
| ~~^~~
blocks.cpp: In member function 'void segment_tree::update(int, int, int, int, int)':
blocks.cpp:16:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
16 | int vm = vl + vr >> 1;
| ~~~^~~~
blocks.cpp: In member function 'long long int segment_tree::query(int, int, int, int, int)':
blocks.cpp:30:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
30 | int vm = vl + vr >> 1;
| ~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
0 ms |
204 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
0 ms |
204 KB |
Output is correct |
| 7 |
Correct |
0 ms |
204 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
0 ms |
204 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
0 ms |
204 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
