This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2")
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const int inf = 1e9;
template<typename T> struct SegTree {
vector<T> tree;
int size;
T neutral_element = 1e9; // sum - 0, mx - (-INF), mn - INF
inline T merge(T a, T b) {
return min(a, b);
}
void init(int n) {
size = 1;
while (size <= n) size *= 2;
tree.assign(2 * size, neutral_element);
}
void build(vector<T> &a) {
size = 1;
while (size < a.size()) size *= 2;
tree.assign(2 * size, neutral_element);
for (int i = size; i < size + a.size(); i++) tree[i] = a[i - size];
for (int i = size - 1; i > 0; i--) tree[i] = merge(tree[i << 1], tree[i << 1 | 1]);
}
void set(int p, T value) { // set value at position p
p += size;
tree[p] = merge(value, tree[p]);
for (; p > 1; p >>= 1) tree[p >> 1] = merge(tree[p], tree[p ^ 1]);
}
T get(int l, int r) { // sum on interval [l, r]
if (l > r) return neutral_element;
T res = neutral_element;
for (l += size, r += size + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) res = merge(res, tree[l++]);
if (r & 1) res = merge(res, tree[--r]);
}
return res;
}
};
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n + 1), left(n + 1), right(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
{
stack<int> st;
for (int i = 1; i <= n; i++) {
while (!st.empty() and a[i] >= a[st.top()]) st.pop();
left[i] = st.empty() ? 0 : st.top();
st.push(i);
}
while (!st.empty()) st.pop();
for (int i = n; i > 0; i--) {
while (!st.empty() and a[i] >= a[st.top()]) st.pop();
right[i] = st.empty() ? n + 1 : st.top();
st.push(i);
}
}
SegTree<int> last; last.init(n + 1);
last.set(0, 0);
for (int len = 1; len <= k; len++) {
vector<vector<int>> out(n + 1);
multiset<int> st;
SegTree<int> sg; sg.init(n + 1);
for (int i = 1; i <= n; i++) {
int x = last.get(left[i], i - 1) + a[i];
out[right[i] - 1].emplace_back(x);
st.insert(x);
sg.set(i, *st.begin());
for (int x: out[i]) st.erase(st.find(x));
}
last = sg;
}
cout << last.get(n, n);
}
int main() {
cin.tie(0)->sync_with_stdio(false);
#ifdef sunnatov
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int q = 1;
// cin >> q;
while (q--) {
solve();
cout << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |