Submission #687590

#TimeUsernameProblemLanguageResultExecution timeMemory
687590speedyArdaK blocks (IZhO14_blocks)C++14
0 / 100
1 ms340 KiB
#include "bits/stdc++.h" using namespace std; using ll = long long; const int MAXN = 1e5+5; ll pref[MAXN], suf[MAXN], in[MAXN]; ll dp[105][MAXN]; ll seg[MAXN * 4]; int n, blocks; void build(int v, int l, int r) { if(l == r) { seg[v] = in[l]; return; } int m = (l + r) / 2; build(2 * v, l, m); build(2 * v + 1, m + 1, r); seg[v] = max(seg[v * 2], seg[v * 2 + 1]); } ll get(int v, int tl, int tr, int l, int r) { if(l > r) return 0; if(l == tl && tr == r) return seg[v]; int tm = (tl + tr) / 2; return max(get(2 * v, tl, tm, l, min(tm, r)), get(2 * v + 1, tm + 1, tr, max(l, tm + 1), r)); } void compute(int l, int r, int optl, int optr, int block) { if(l > r) return; int mid = (l + r) / 2; pair<ll, int> best = {1e18, -1}; for(int k = optl; k <= min(mid, optr); k++) { best = min(best, {(k ? dp[block - 1][k - 1] : 0) + get(1, 0, n - 1, k, mid), k}); //cout << k << " " << mid << " " << get(1, 0, n-1, k, mid) << " " << best.first << "\n"; } dp[block][mid] = best.first; int opt = best.second; //cout << block << " " << mid << " " << dp[block][mid] << "\n"; compute(l, mid - 1, optl, opt, block); compute(mid + 1, r, opt, optr, block); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> blocks; vector<int> max_idx; pref[0] = suf[n+1] = 0; for(int i = 0; i < n; i++) { cin >> in[i]; } build(1, 0, n - 1); for(int i = 0; i < n; i++) dp[1][i] = get(1, 0, n - 1, 0, i); //cout << "hm\n"; for(int block = 2; block <= blocks; block++) { compute(block - 1, n - 1, block - 1, n - 1, block); } cout << dp[blocks][n - 1] << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...