# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1077213 | Wjsc | K blocks (IZhO14_blocks) | C++14 | 216 ms | 84736 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;
#define int long long
#define pi pair<int, int>
#define fi first
#define se second
#define all(v) v.begin(), v.end()
const int N = 1e5 + 5,
M = 1e2 + 5,
INF = 1e18;
int n, k;
int a[N];
int f[N][M];
signed main() {
cin.tie(0)->sync_with_stdio(0);
if(fopen("task.inp", "r")) {
freopen("task.inp", "r", stdin);
freopen("task.out", "w", stdout);
}
memset(f, 120, sizeof f);
cin >> n >> k;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
if(i == 1) f[i][1] = a[i];
else f[i][1] = max(f[i - 1][1], a[i]);
}
for(int j = 2; j <= k; ++j) {
stack<pi> st;
for(int i = 1; i <= n; ++i) {
int c = INF;
while(st.size() && a[st.top().fi] <= a[i]) {
f[i][j] = min(f[i][j], f[st.top().fi][j - 1] + a[i]);
f[i][j] = min(f[i][j], st.top().se + a[i]);
c = min(c, st.top().se);
c = min(c, f[st.top().fi][j - 1]);
st.pop();
}
if(st.size()) {
f[i][j] = min(f[i][j], f[st.top().fi][j]);
f[i][j] = min(f[i][j], f[st.top().fi][j - 1] + a[i]);
}
st.push({i, c});
}
}
cout << f[n][k];
}
Compilation message (stderr)
# | 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... |