Submission #1208106

#TimeUsernameProblemLanguageResultExecution timeMemory
1208106gatapdevK blocks (IZhO14_blocks)C++20
0 / 100
0 ms328 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const ll INF = LLONG_MAX / 4; // Segment tree supporting range-add and range-min queries struct SegTree { int n; vector<ll> st, lazy; SegTree(int _n) : n(_n), st(4 * n, INF), lazy(4 * n, 0) {} void apply(int p, int l, int r, ll v) { st[p] += v; lazy[p] += v; } void push(int p, int l, int r) { if (lazy[p] != 0) { int m = (l + r) >> 1; apply(p << 1, l, m, lazy[p]); apply(p << 1 | 1, m + 1, r, lazy[p]); lazy[p] = 0; } } void pull(int p) { st[p] = min(st[p << 1], st[p << 1 | 1]); } void build(int p, int l, int r, const vector<ll>& base) { if (l == r) { st[p] = base[l]; return; } int m = (l + r) >> 1; build(p << 1, l, m, base); build(p << 1 | 1, m + 1, r, base); pull(p); } void range_add(int p, int l, int r, int i, int j, ll v) { if (i > r || j < l) return; if (i <= l && r <= j) { apply(p, l, r, v); return; } push(p, l, r); int m = (l + r) >> 1; range_add(p << 1, l, m, i, j, v); range_add(p << 1 | 1, m + 1, r, i, j, v); pull(p); } ll range_min(int p, int l, int r, int i, int j) { if (i > r || j < l) return INF; if (i <= l && r <= j) return st[p]; push(p, l, r); int m = (l + r) >> 1; return min( range_min(p << 1, l, m, i, j), range_min(p << 1 | 1, m + 1, r, i, j) ); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, K; cin >> n >> K; vector<ll> a(n + 1); for (int i = 1; i <= n; i++) cin >> a[i]; // dp_prev[j]: best cost for up to j with prev segments vector<ll> dp_prev(n + 1, INF), dp_cur(n + 1, INF); dp_prev[0] = 0; // Base case k=1: prefix max for (int i = 1; i <= n; i++) { dp_prev[i] = max(dp_prev[i - 1], a[i]); } for (int k = 2; k <= K; k++) { // Build segment tree on dp_prev SegTree st(n + 1); st.build(1, 0, n, dp_prev); vector<int> stk, left(n + 1); stk.reserve(n); fill(dp_cur.begin(), dp_cur.end(), INF); for (int i = 1; i <= n; i++) { int L = i; // Pop smaller or equal elements, update range while (!stk.empty() && a[stk.back()] <= a[i]) { int t = stk.back(); stk.pop_back(); int lt = left[t]; st.range_add(1, 0, n, lt - 1, t - 1, a[i] - a[t]); L = lt; } stk.push_back(i); left[i] = L; // Query best dp for pos i with k segments dp_cur[i] = st.range_min(1, 0, n, 0, i - 1); } dp_prev.swap(dp_cur); } cout << dp_prev[n] << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...