Submission #1239256

#TimeUsernameProblemLanguageResultExecution timeMemory
1239256sh1ftSplit the sequence (APIO14_sequence)C++17
33 / 100
24 ms5448 KiB
/* author : sh1ft created : 12/07/2025 22:43 task : APIO14_sequence */ #include <bits/stdc++.h> #define ll long long using namespace std; const int mxN = 1e5+5, mxK = 205; int n, k; ll dp[mxK][mxN], p[mxN], par[mxK][mxN]; int main() { ios::sync_with_stdio(0), cin.tie(0); cin >> n >> k; for (int i = 1; i <= n; i++) cin >> p[i], p[i] += p[i-1]; for (int i = 1; i <= n; i++) dp[1][i] = p[i]*(p[n] - p[i]); for (int c = 2; c <= k; c++) { deque <int> cht; int sz = 0; cht.emplace_back(c-1), sz++; auto calc = [&] (int j, ll x) { return p[j]*x + -p[j]*p[n] + dp[c-1][j]; }; auto m = [&] (int x, int y) { return (long double) (calc(x, 0) - calc(y, 0)) / (p[y] - p[x]); }; for (int i = c; i <= n; i++) { while (sz > 1 && calc(cht[0], p[i]) <= calc(cht[1], p[i])) cht.pop_front(), sz--; dp[c][i] = p[i]*(p[n]-p[i]) + calc(cht[0], p[i]); par[c][i] = cht[0]; while (sz > 1 && m(cht[sz-1], i) <= m(cht[sz-1], cht[sz-2])) cht.pop_back(), sz--; cht.emplace_back(i), sz++; } } ll mx = 0, idx = -1; for (int i = k; i < n; i++) if (dp[k][i] >= mx) mx = dp[k][i], idx = i; cout << mx << '\n'; for (int i = k; i > 0; i--) cout << idx << ' ', idx = par[i][idx]; cout << '\n'; } /* dp[c][i] = max((p[i] - p[j])*(p[n] - p[i]) + dp[c-1][j]) = p[i]*(p[n]-p[i]) + max(p[j](p[i]) + -p[j]*p[n] + dp[c-1][j]) */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...