//{ <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], v[N], p[N], f[N];
inline int mx(int l, int r) {
if(l > r) re 0;
int f = lg[r - l + 1];
re max(st[f][l], st[f][r - pw(f) + 1]);
}
void fupd(int i, int v) {for(i = N - i - 1; i < N; i += i & -i) umin(f[i], v);}
int fget(int i) {int v = oo; for(i = N - i - 1; i; i -= i & -i) umin(v, f[i]); re v;}
void solve() {
cin >> n >> k;
fo(n) cin >> a[i], p[i] = i;
sort(p, p + n, [&] (int x, int y) {re a[x] < a[y];});
fo(n) v[p[i]] = i ? v[p[i - 1]] + (a[p[i - 1]] != a[p[i]]) : 1;
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)]);
if(k == 1) re void(cout << mx(0, n - 1) << endl);
fo(n) {
int l = 0, r = i;
while(l < r) {
int m = (l + r + 1) >> 1;
mx(i - m - 1, i - 1) >= a[i]
? r = m - 1
: l = m;
}
c[i] = l;
}
int dp[k - 1][n];
fo(n) dp[0][i] = mx(0, i);
fo(k - 1) if(i) {
clr(f, 127);
fr(j, n) {
dp[i][j] = oo;
if(j < i) continue;
if(j && a[j - 1] >= a[j]) umin(dp[i][j], dp[i][j - 1]);
if(j && a[j - 1] < a[j]) umin(dp[i][j], dp[i][j - 1] + a[j] - a[j - 1]);
for(int p = j - c[j] - 1; p < j; ++p) if(p >= 0)
umin(dp[i][j], dp[i - 1][p] + a[j]);
}
}
#ifdef _LOCAL
fr(j, k - 1) fo(n) cerr << dp[j][i] << (i == n - 1 ? '\n' : ' ');
#endif
int ans = oo;
fo(n - 1) umin(ans, dp[k - 2][i] + mx(i + 1, n - 1));
cout << ans << 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 |
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 |
380 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 |
380 KB |
Output is correct |
| 9 |
Correct |
2 ms |
760 KB |
Output is correct |
| 10 |
Correct |
2 ms |
760 KB |
Output is correct |
| 11 |
Incorrect |
2 ms |
760 KB |
Output isn't correct |
| 12 |
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 |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
760 KB |
Output is correct |
| 10 |
Correct |
2 ms |
760 KB |
Output is correct |
| 11 |
Incorrect |
2 ms |
760 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
364 ms |
2424 KB |
Output is correct |
| 2 |
Correct |
11 ms |
3576 KB |
Output is correct |
| 3 |
Execution timed out |
1067 ms |
5204 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
