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;
typedef long long ll;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector <ll> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector <vector <ll>> dp(k + 1, vector <ll> (n, 1e15));
dp[1][0] = a[0];
ll mx = a[0];
for (int i = 1; i < n; i++) {
if (a[i] < mx) continue;
dp[1][i] = a[i];
mx = a[i];
}
for (int step = 2; step <= k; step++) {
vector <ll> u(n, 1e15), f(n, 1e15);
vector <int> st;
for (int i = 0; i < n; i++) {
while (!st.empty() && a[st.back()] < a[i]) {
u[i] = min(u[i], u[st.back()]);
u[i] = min(u[i], dp[step - 1][st.back()]);
st.pop_back();
}
dp[step][i] = min(dp[step][i], u[i] + a[i]);
f[i] = dp[step - 1][i];
if (!st.empty()) {
dp[step][i] = min(dp[step][i], f[st.back()] + a[i]);
f[i] = min(f[i], f[st.back()]);
}
st.push_back(i);
}
}
ll ans = dp[k][n - 1];
mx = a[n - 1];
for (int i = n - 2; i >= 0; i--) {
if (mx > a[i]) continue;
ans = min(ans, dp[k][i]);
mx = a[i];
}
cout << ans << "\n";
return 0;
}
# | 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... |