//{ <defines>
#ifndef _LOCAL
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#endif
#include <bits/stdc++.h>
using namespace std;
#define fr(i, n) for(int i = 0; i < n; ++i)
#define fo(n) fr(i, n)
#define re return
#define ef else if
#define ifn(x) if(!(x))
#define _ << ' ' <<
#define ft first
#define sd second
#define ve vector
#define pb push_back
#define eb emplace_back
#define sz(x) int(x.size())
#define pw(x) (1 << (x))
#define PW(x) (1ll << (x))
#define bnd(x) x.begin(), x.end()
#define clr(x, y) memset(x, y, sizeof x)
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef ve<int> vi;
const int oo = 2e9;
const ll OO = 4e18;
//const ld pi = arg(complex<ld>(-1, 0));
//const ld pi2 = pi + pi;
const int md = 0x3b800001;
const int MD = 1e9 + 7;
inline ll time() {re chrono :: system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
mt19937_64 RND(time());
template<typename t> inline void umin(t &a, t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, t b) {a = max(a, b);}
//} </defines>
const int N = 1e5 + 5;
const int LG = 18;
int n, k, a[N], lg[N], st[LG][N], c[N];
inline int mx(int l, int r) {
int f = lg[r - l + 1];
re max(st[f][l], st[f][r - pw(f) + 1]);
}
struct tree {
tree *l, *r;
int v, p;
tree(int tl = 0, int tr = n - 1): l(r = 0), v(oo), p(0) {
if(tl < tr) {
int tm = (tl + tr) >> 1;
l = new tree(tl, tm);
r = new tree(tm + 1, tr);
}
}
inline void push() {
ifn(p) re;
if(l) l -> p += p;
if(r) r -> p += p;
if(v < oo) v += p;
p = 0;
}
void assign(int i, int p, int tl = 0, int tr = n - 1) {
push();
if(tl == tr) re void(v = p);
int tm = (tl + tr) >> 1;
i <= tm
? l -> assign(i, p, tl, tm)
: r -> assign(i, p, tm + 1, tr);
v = min(l -> v, r -> v);
}
int req(int ql, int qr, int tl = 0, int tr = n - 1) {
push();
if(ql == tl && qr == tr) re v;
if(ql > qr) re oo;
int tm = (tl + tr) >> 1;
re min(l -> req(ql, min(tm, qr), tl, tm),
r -> req(max(ql, tm + 1), qr, tm + 1, tr));
}
void clear() {
if(l) l -> clear();
if(r) r -> clear();
v = oo; p = 0;
}
void add(int pp, int ql, int qr, int tl = 0, int tr = n - 1) {
if(ql == tl && qr == tr) re (p += pp, push());
push();
if(ql > qr) re;
int tm = (tl + tr) >> 1;
l -> add(pp, ql, min(tm, qr), tl, tm);
r -> add(pp, max(ql, tm + 1), qr, tm + 1, tr);
v = min(l -> v, r -> v);
}
};
void solve() {
cin >> n >> k;
fo(n) cin >> a[i];
tree t = *new tree();
copy(a, a + n, st[0]);
fo(n + 1) lg[i] = i ? lg[i - 1] + (pw(lg[i - 1] + 1) <= i) : 0;
fo(LG) if(i) for(int j = 0; j + pw(i) - 1 < n; ++j) st[i][j] = max(st[i - 1][j], st[i - 1][j + pw(i - 1)]);
int dp[k][n];
fo(n) dp[0][i] = mx(0, i);
fr(j, k) if(j) {
t.clear();
vi f;
fo(n) {
dp[j][i] = oo;
if(i < j) continue;
for(; !f.empty() && a[f.back()] <= a[i]; f.pop_back()) {
t.add(a[i] - a[f.back()], f.size() == 1 ? j : f.back() - 1, i - 1);
}
f.pb(i);
t.assign(i, dp[j - 1][i - 1] + a[i]);
dp[j][i] = t.v;
// fr(p, n) cerr << t.req(p, p) << (p == n - 1 ? '\n' : ' ');
}
}
#ifdef _LOCAL
int ch[k][n];
fo(n) ch[0][i] = mx(0, i);
fr(j, k) if(j) {
fo(n) {
ch[j][i] = oo;
if(i < j) continue;
fr(t, i) umin(ch[j][i], ch[j - 1][t] + mx(t + 1, i));
}
}
fo(k) fr(j, n) if((dp[i][j] >= oo ? -1 : dp[i][j]) != (ch[i][j] >= oo ? -1 : ch[i][j])) cerr << "srak\n";
fo(k) fr(j, n) cerr << (dp[i][j] >= oo ? -1 : dp[i][j]) << (j == n - 1 ? '\n' : ' ');
fo(k) fr(j, n) cerr << (ch[i][j] >= oo ? -1 : ch[i][j]) << (j == n - 1 ? '\n' : ' ');
#endif
cout << dp[k - 1][n - 1] << endl;
}
int main() {
#ifdef _LOCAL
freopen("in.txt", "r", stdin);
int tests; cin >> tests;
fo(tests) {
cerr << "case #" << i+1 << endl;
solve();
}
#else
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
solve();
#endif
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
0 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
380 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
83 ms |
2516 KB |
Output is correct |
| 2 |
Correct |
14 ms |
6264 KB |
Output is correct |
| 3 |
Incorrect |
117 ms |
7288 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
