# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
166136 | ZwariowanyMarcin | Split the sequence (APIO14_sequence) | C++14 | 1581 ms | 81912 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define ld long double
#define ss(x) (int) x.size()
#define FOR(i, n) for(int i = 1; i <= n; ++i)
#define fi first
#define se second
#define cat(x) cout << #x << " = " << x << endl
using namespace std;
const int nax = 1e5 + 111;
const long long inf = 1e18;
int n, k;
int a[nax];
ll dp[nax][2];
int opt[nax][202];
int pref[nax];
int ja, on, K;
void solve(int l, int r, int optl, int optr) {
if(l > r) return;
int m = (l + r) / 2;
opt[m][K] = 1;
for(int i = optl; i <= min(m, optr); ++i) {
ll w = dp[i - 1][on] + 1ll * (pref[m] - pref[i - 1]) * (pref[m] - pref[i - 1]);
if(w <= dp[m][ja]) {
opt[m][K] = i;
dp[m][ja] = w;
}
}
solve(l, m - 1, optl, opt[m][K]);
solve(m + 1, r, opt[m][K], optr);
}
int main() {
scanf("%d %d", &n, &k);
k += 1;
for(int i = 1; i <= n; ++i) {
scanf("%d", a + i);
pref[i] = pref[i - 1] + a[i];
}
for(int i = 1; i <= n; ++i)
dp[i][0] = inf;
for(int i = 1; i <= k; ++i) {
K = i;
ja = i & 1;
on = !ja;
for(int j = 0; j <= n; ++j)
dp[j][ja] = inf;
solve(1, n, 1, n);
}
ll kwa = 1ll * pref[n] * pref[n];
printf("%lld\n", (kwa - dp[n][k & 1]) / 2);
vector <int> v;
int ind = n;
while(k > 1) {
v.pb(opt[ind][k]);
ind = opt[ind][k] - 1;
k -= 1;
}
reverse(v.begin(), v.end());
for(auto it : v)
printf("%d ", it - 1);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |