| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 487895 | SirCovidThe19th | K blocks (IZhO14_blocks) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int mx = 2e5 + 5;
int n, k, A[mx]; stack<int> stk;
struct Node{ long long mnDP, vDP; int vRange; };
template<int sz> struct ST{
Node seg[sz * 4]; int lz[sz * 4];
inline Node comb(Node a, Node b){
if (a.vDP + a.vRange > b.vDP + b.vRange) swap(a, b);
a.mnDP = min(a.mnDP, b.mnDP);
return a;
}
inline Node comb1(int i, int j){
Node a = seg[i], b = seg[j];
if (lz[i]) a.vDP = a.mnDP, a.vRange = lz[i];
if (lz[j]) b.vDP = b.mnDP, b.vRange = lz[j];
return comb(a, b);
}
inline void push(int l, int r, int i){
if (!lz[i]) return;
seg[i].vRange = lz[i];
if (l != r) lz[i * 2] = lz[i * 2 + 1] = lz[i];
lz[i] = 0;
}
inline void upd(int x, int y, int vDP, int vR, int l = 0, int r = sz, int i = 1){
push(l, r, i);
if (l > y or r < x) return;
if (l >= x and r <= y){
if (vDP) seg[i].mnDP = seg[i].vDP = vDP;
if (vR) lz[i] = vR, push(l, r, i);
return;
}
int mid = (l + r) / 2;
upd(x, y, vDP, vR, l, mid, i * 2); upd(x, y, vDP, vR, mid + 1, r, i * 2 + 1);
seg[i] = comb1(i * 2, i * 2 + 1);
}
inline Node query(int x, int y, int l = 0, int r = sz, int i = 1){
push(l, r, i);
if (l > y or r < x) return {(int)1e9, (int)1e9};
if (l != r) seg[i] = comb1(i * 2, i * 2 + 1); //reupd
if (l >= x and r <= y) return seg[i];
int mid = (l + r) / 2;
return comb(query(x, y, l, mid, i * 2), query(x, y, mid + 1, r, i * 2 + 1));
}
};ST<mx> dp[101];
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> k;
for (int j = 1; j <= k; j++) dp[j].upd(0, 0, 1e9, 0);
for (int i = 1; i <= n; i++) dp[0].upd(i, i, 1e9, 0);
for (int i = 1; i <= n; i++){
cin >> A[i];
while (!stk.empty() and A[stk.top()] < A[i]) stk.pop();
int L = (stk.empty()) ? 0 : stk.top();
for (int j = 1; j <= k; j++){
dp[j - 1].upd(L, i - 1, 0, A[i]);
Node ret = dp[j - 1].query(0, i - 1);
long long ans = ret.vDP + ret.vRange;
dp[j].upd(i, i, ans, 0);
if (i == n and j == k) cout<<ans<<endl;
}
stk.push(i);
}
}