| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 543567 | 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;
inline namespace _LineContainer { //Line Container copied from USACO Guide
bool _Line_Comp_State;
struct Line {
// k is slope, m is intercept, p is intersection point
mutable long long k, m, p;
bool operator<(const Line& o) const {
return _Line_Comp_State ? p < o.p : k < o.k;
}
};
struct LineContainer : multiset<Line> {
long long div(long long a, long long b) { return a / b - ((a ^ b) < 0 && a % b); }
bool isect(iterator x, iterator y) {
if (y == end()) {
x->p = LLONG_MAX;
return false;
}
if (x->k == y->k)
x->p = x->m > y->m ? LLONG_MAX : -LLONG_MAX;
else
x->p = div(y->m - x->m, x->k - y->k);
return x->p >= y->p;
}
void add(long long k, long long m) {
auto z = insert({k, m, 0}), y = z++, x = y;
while (isect(y, z))
z = erase(z);
if (x != begin() && isect(--x, y))
isect(x, y = erase(y));
while ((y = x) != begin() && (--x)->p >= y->p)
isect(x, erase(y));
}
long long query(long long x) {
assert(!empty());
_Line_Comp_State = 1;
auto l = *lower_bound({0,0,x});
_Line_Comp_State = 0;
return l.k * x + l.m;
}
};
}
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++) {
LineContainer 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]), (int64_t)0) + 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;
}
}
}