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 ll long long
#define f first
#define s second
#define sz(a) (int)(a.size())
#define all(a) a.begin(), a.end()
#define uni(a) sort(all(a)), a.resize(unique(all(a)) - a.begin())
typedef pair <int, int> ii;
const int N = 1e5 + 5;
int n, k, a[N], ans, l[N], r[N], dp[101][N];
stack <int> st;
int mn[N][20];
int *save;
void build() {
for (int i = 0; i <= n; i++) mn[i][0] = save[i];
for (int j = 1; (1 << j) <= n; j++) {
for (int i = 0; i + (1 << j) - 1 <= n; i++) {
mn[i][j] = min(mn[i][j - 1], mn[i + (1 << j - 1)][j - 1]);
}
}
}
int get(int l, int r) {
if (l > r) return 1e9;
int lg = __lg(r - l + 1);
return min(mn[l][lg], mn[r - (1 << lg) + 1][lg]);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//freopen("a.inp", "r", stdin);
//freopen("a.out", "w", stdout);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
a[0] = a[n + 1] = 1e9;
st.push(0);
for (int i = 1; i <= n; i++) {
while (a[st.top()] <= a[i]) st.pop();
l[i] = st.top();
st.push(i);
}
while (sz(st)) st.pop();
st.push(n + 1);
for (int i = n; i >= 1; i--) {
while (a[st.top()] <= a[i]) st.pop();
r[i] = st.top();
st.push(i);
}
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = 0; save = dp[0];
for (int j = 1; j <= k; j++) {
build();
for (int i = 1; i <= n; i++) {
dp[j][i] = get(l[i], i - 1) + a[i];
dp[j][i] = min(dp[j][i], dp[j][l[i]]);
}
save = dp[j];
}
cout << dp[k][n] << '\n';
return 0;
}
Compilation message (stderr)
blocks.cpp: In function 'void build()':
blocks.cpp:25:57: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
25 | mn[i][j] = min(mn[i][j - 1], mn[i + (1 << j - 1)][j - 1]);
| ~~^~~
# | 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... |