# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1148626 | blackslex | Split the sequence (APIO14_sequence) | C++20 | 2094 ms | 24644 KiB |
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
int n, k;
int main() {
scanf("%d %d", &n, &k);
vector<int> a(n + 5), pref(n + 5);
vector<vector<ll>> dp(k + 5, vector<ll>(n + 5));
vector<vector<int>> par(k + 5, vector<int>(n + 5));
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
pref[i] = pref[i - 1] + a[i];
}
auto get = [&] (int l, int r) {
return pref[r] - pref[l - 1];
};
for (int i = 1; i < n; i++) {
dp[1][i] = 1LL * get(1, i) * get(i + 1, n);
par[1][i] = i;
}
for (int i = 2; i <= k; i++) {
for (int j = 2; j < n; j++) {
for (int l = 1; l < j; l++) {
ll nval = dp[i - 1][l] + 1LL * get(l + 1, j) * get(j + 1, n);
if (nval >= dp[i][j]) {
dp[i][j] = nval;
par[i][j] = l;
}
}
}
}
pii xx = {0, 0};
for (int i = 1; i < n; i++) xx = max(xx, {dp[k][i], i});
vector<pii> u{{k, xx.second}};
while (u.back().first != 1) {
auto [x, y] = u.back();
u.emplace_back(x - 1, par[x][y]);
}
reverse(u.begin(), u.end());
printf("%lld\n", xx.first);
for (auto &[x, y]: u) printf("%d ", y);
}
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... |