# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
31975 | minimario | Split the sequence (APIO14_sequence) | C++14 | 2000 ms | 87568 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>
using namespace std;
const int MAX = 100005;
typedef long long ll;
typedef pair<ll, ll> pii;
#define f first
#define s second
pii line[MAX];
int orig[MAX];
double hit[MAX];
int ct = 0;
double sect(pii l1, pii l2) {
// l1.f * x + l1.s = l2.f * x + l2.s
return (double)(l2.s - l1.s) / (double)(l1.f - l2.f);
}
int ptr = 1;
void add(ll m, ll b, int k) {
pii l = {m, b};
// l and line[2] > hit[2]
while (ct > 1) {
if (l.f != line[ct].f && sect(l, line[ct]) > hit[ct]) { break; }
ct--;
}
ct++;
ptr = min(ptr, ct);
orig[ct] = k;
line[ct] = l;
if (ct != 1) { hit[ct] = sect(l, line[ct-1]); }
}
pii eval(ll x) {
pii l; int ind = -1;
if (ct == 0) { return {0, 0}; }
if (ct == 1) {
ptr = 1;
l = line[1];
ind = orig[1];
}
else {
while (hit[ptr] < x) { ptr++; }
ptr--;
l = line[ptr];
ind = orig[ptr];
}
return {(ll)l.f * (ll)x + (ll)l.s, ind};
}
int a[MAX];
ll p[MAX];
ll dp[MAX][2];
int last[MAX][205];
int main() {
//freopen("a.in", "r", stdin);
//freopen("a.out", "w", stdout);
int n, k0; scanf("%d %d", &n, &k0);
for (int i=1; i<=n; i++) {
scanf("%d", &a[i]);
p[i] = (ll)p[i-1] + (ll)a[i];
}
for (int k=1; k<=k0+1; k++) {
ct = 0;
for (int i=k-1; i<=n; i++) {
if (k == 1) {
dp[i][k] = 0;
}
else {
add(-p[i], -(ll)dp[i][(k+1)%2]+(ll)p[i]*(ll)p[i], i);
if (i != k-1) {
dp[i][k%2] = -eval(p[i]).f;
last[i][k] = (int)eval(p[i]).s;
}
}
}
}
k0++;
printf("%lld\n", dp[n][k0%2]);
while (k0 != 1) {
int bef = last[n][k0];
printf("%d ", bef);
n = bef; k0--;
}
}
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... |