| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1101700 |
2024-10-16T15:58:36 Z |
trie |
K blocks (IZhO14_blocks) |
C++17 |
|
1 ms |
2552 KB |
#include<bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
#define ii pair<int, int>
#define iii pair<ii, int>
#define ll long long
#define pb push_back
#define pli pair<ll, int>
#define all(v) (v).begin(), (v).end()
#define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define cntbit(mask) __builtin_popcount(mask)
#define getbit(x, i) ((x >> i) & 1)
#define MASK(i) (1 << i)
#define pli pair<ll, int>
using namespace std;
template<class T1, class T2>
bool maximize(T1 &a, T2 b){if(a < b){a = b; return 1;} return 0;}
template<class T1, class T2>
bool minimize(T1 &a, T2 b){if(a > b){a = b; return 1;} return 0;}
const int N = 1e5 + 5;
const int V = 105;
const int MOD = 1e9 + 7;
const int LOG = 19;
int n, k, a[N], rmq[N][20];
ll dp[2][N];
int Cost(int i, int j) {
int p = __lg(j - i + 1);
return max(rmq[i][p], rmq[j - MASK(p) + 1][p]);
}
void calc(int u, int v, int l, int r, int cur) {
if (l > r) return;
int best = -1, m = (r + l) / 2;
dp[cur][m] = 1e18;
for(int i = u ; i <= min(m, v) ; i++)
if (minimize(dp[cur][m], dp[1 - cur][i] + Cost(i + 1, m))) best = i;
calc(u, best, l, m - 1, cur);
calc(best, v, m + 1, r, cur);
}
void solve() {
cin >> n >> k;
for(int i = 1 ; i <= n ; i++) cin >> a[i];
for(int i = 1 ; i <= n ; i++) rmq[i][0] = a[i];
for(int j = 1 ; j <= LOG ; j++)
for(int i = 1 ; i <= n - MASK(j) + 1 ; i++)
rmq[i][j] = max(rmq[i][j - 1], rmq[i + MASK(j - 1)][j - 1]);
for(int i = 1 ; i <= n ; i++) dp[1][i] = Cost(1, i);
for(int i = 2 ; i <= k ; i++) calc(1, n, 1, n, i & 1);
cout << dp[k & 1][n];
}
int main(void) {
//freopen("task.inp", "r", stdin);
//freopen("task.out", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t = 1; while(t--) solve();
return 0;
}
Compilation message
blocks.cpp: In function 'void solve()':
blocks.cpp:53:59: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
53 | rmq[i][j] = max(rmq[i][j - 1], rmq[i + MASK(j - 1)][j - 1]);
| ~~^~~
blocks.cpp:14:23: note: in definition of macro 'MASK'
14 | #define MASK(i) (1 << i)
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 10 |
Incorrect |
1 ms |
2384 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2552 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 10 |
Incorrect |
1 ms |
2384 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 10 |
Incorrect |
1 ms |
2384 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 10 |
Incorrect |
1 ms |
2384 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
