#include <bits/stdc++.h>
#define F(i, a, b) for(int i = (a); i <= (b); ++i)
#define R(i, a, b) for(int i = (a); i >= (b); --i)
#define N(a) (int)a.size()
using namespace std;
void read(int &n) {
n = 0;
char c = getchar();
while(isdigit(c)) {
(n *= 10) += c - '0';
c = getchar();
}
}
const int maxn = 1e5 + 1;
int n, k, cnt, a[maxn], s[maxn][2], dp[maxn], tdp[maxn];
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
read(n), read(k);
F(i, 1, n) read(a[i]), dp[i] = max(dp[i - 1], a[i]);
F(_k, 2, k) {
cnt = 0;
memset(tdp, 63, sizeof tdp);
F(i, _k, n) {
static int min_f;
min_f = dp[i - 1];
while(cnt && a[s[cnt][0]] <= a[i]) {
min_f = min(min_f, s[cnt][1]);
--cnt;
}
tdp[i] = min_f + a[i];
if(cnt) tdp[i] = min(tdp[i], tdp[s[cnt][0]]);
++cnt;
s[cnt][0] = i, s[cnt][1] = min_f;
}
swap(tdp, dp);
}
cout << dp[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... |