| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 543562 | Olympia | Split the sequence (APIO14_sequence) | C++17 | 0 ms | 0 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 <vector>
#include <algorithm>
#include <iostream>
#include <set>
#include <cmath>
#include <map>
#include <random>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <limits.h>
using namespace std;
const int64_t inf = -(1LL << 62);
struct line {
int64_t m, b;
mutable function<const line*() > succ;
bool operator < (const line& rhs) const {
if (rhs.b != inf) return m < rhs.m;
const line* s = succ();
if (!s) return 0;
int64_t x = rhs.m;
return b - s->b < (s->m - m) * x;
}
};
struct CHT : public multiset<line> {
bool bad(iterator y) {
auto z = next(y);
if (y == begin()) {
if (z == end()) return 0;
return y -> m == z -> m && y -> b <= z -> b;
}
auto x = prev(y);
if (z == end()) return y -> m == x -> m && y -> b <= x -> b;
return 1.0 * (x -> b - y -> b) * (z -> m - y -> m) >= 1.0 * (y -> b - z -> b) * (y -> m - x -> m);
}
void add(int64_t m, int64_t b) {
auto y = insert({ m, b });
y->succ = [ = ] { return next(y) == end() ? 0 : &*next(y); };
if (bad(y)) {
erase(y);
return;
}
while (next(y) != end() && bad(next(y))) erase(next(y));
while (y != begin() && bad(prev(y))) erase(prev(y));
}
int64_t query(int64_t x) {
assert(!empty());
auto l = *lower_bound((line) {x, inf});
return l.m * x + l.b;
}
};
int main () {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, k;
cin >> n >> k;
int64_t arr[n]; int64_t pref[n + 1]; pref[0] = 0;
for (int i = 0; i < n; i++) {
cin >> arr[i];
pref[i + 1] = pref[i] + arr[i];
}
int64_t dp[n - 1][k + 1];
int64_t prev[n - 1][k + 1];
for (int i = 0; i < n - 1; i++) {
dp[i][1] = (pref[i + 1]) * (pref[n] - pref[i + 1]);
prev[i][1] = -1;
}
for (int j = 2; j <= k; j++) {
CHT cht;
dp[0][j] = 0;
for (int i = 1; i < n - 1; i++) {
cht.add(pref[i], dp[i - 1][j - 1]);
dp[i][j] = 0;
int64_t extra = pref[i + 1] * pref[n] - pref[i + 1] * pref[i + 1];
for (int pre = 0; pre < i; pre++) {
int64_t tot = dp[pre][j - 1] + pref[pre + 1] * (pref[i + 1] - pref[n]) ;
if (tot >= dp[i][j]) {
prev[i][j] = pre;
}
}
dp[i][j] = max(cht.query(pref[i + 1] - pref[n]), 0ll) + extra;
}
}
int64_t myMax = 0;
for (int i = 0; i < n - 1; i++) {
myMax = max(myMax, dp[i][k]);
}
cout << myMax << '\n';
for (int i = 0; i < n - 1; i++) {
if (myMax == dp[i][k]) {
int mid = i;
int cntr = 0;
while (cntr != k) {
cout << mid + 1 << ' ';
mid = prev[mid][k - cntr];
cntr++;
}
return 0;
}
}
}