Submission #676584

#TimeUsernameProblemLanguageResultExecution timeMemory
676584benjaminkleynSplit the sequence (APIO14_sequence)C++17
100 / 100
649 ms82124 KiB
#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx,avx2,fma") #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; int N, K, a[100001]; ll pref[100001] = {0}; ll dp[2][100001] = {0}; int last_split[202][100001]; int cht[100001], fr = 0, bk = -1; #define m(j) (pref[j]) #define c(j) (dp[0][j]-pref[j]*pref[N]) inline ld isect(const int &a, const int &b) { return (ld)(c(b) - c(a)) / (ld)(m(a) - m(b)); } inline bool bad(const int &x, const int &y, const int &z) { return isect(z, y) <= isect(z, x); } inline ll eval(const int &i, const ll &x) { return m(i) * x + c(i); } int main() { cin.tie(0)->sync_with_stdio(0); cin >> N >> K; for (int i = 1; i <= N; i++) { cin >> a[i]; pref[i] = pref[i-1] + a[i]; } for (int i = 0; i <= N; i++) dp[0][i] = pref[i] * (pref[N] - pref[i]); for (int k = 2; k <= K + 1; k++) { fr = 0, bk = -1; for (int i = k; i <= N; i++) { while (fr < bk && bad(cht[bk-1], cht[bk], i-1)) bk--; cht[++bk] = i-1; while (fr < bk && eval(cht[fr], pref[i]) <= eval(cht[fr+1], pref[i])) fr++; dp[1][i] = eval(cht[fr], pref[i]) + pref[i] * (pref[N] - pref[i]); last_split[k][i] = cht[fr]; } swap(dp[0], dp[1]); } cout << dp[0][N] << '\n'; int i = N; do { i = last_split[K+1][i]; cout << i << ' '; } while (--K); cout << '\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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...