//{ <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) {
if(l > r) re 0;
int f = lg[r - l + 1];
re max(st[f][l], st[f][r - pw(f) + 1]);
}
void solve() {
cin >> n >> k;
fo(n) cin >> a[i];
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 + 1;
while(l < r) {
int m = (l + r + 1) >> 1;
mx(i - m, 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) {
fr(j, n) {
dp[i][j] = oo;
if(j < i) continue;
for(int p = j - c[j]; p < j; ++p) if(~p)
umin(dp[i][j], dp[i - 1][p] + a[j]);
}
}
// fr(j, k - 1) fo(n) cerr << dp[j][i] << (i == n - 1 ? '\n' : ' ');
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 |
296 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 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 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 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 10 |
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 |
Execution timed out |
1070 ms |
2004 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
