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> pll;
#define f first
#define s second
pll line[MAX];
int orig[MAX];
int ct = 0;
int ptr = 0;
bool bad(pll l0, pll l1, pll l2) {
return (l1.s-l0.s)*(l0.f-l2.f) >= (l0.f-l1.f)*(l2.s-l0.s);
}
ll f(pll l, ll x) {
return l.f * x + l.s;
}
void add(pll l, int i) {
while (ct >= 2 && bad(line[ct-1], line[ct], l)) {
ct--;
}
ptr = min(ptr, ct);
ct++;
line[ct] = l;
orig[ct] = i;
}
pair<ll, int> get(ll x) {
ptr = max(ptr, 1);
if (ct == 0) { return {0, 0}; }
while (ptr < ct && f(line[ptr], x) < f(line[ptr+1], x)) {
ptr++;
}
return {f(line[ptr], x), orig[ptr]};
}
int a[MAX];
ll p[MAX];
ll dp[MAX][2];
int last[MAX][205];
int main() {
// double c = clock();
//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) {
pll ans = get(p[i]);
dp[i][k%2] = ans.f;
last[i][k] = (int)ans.s;
}
}
}
}
k0++;
printf("%lld\n", dp[n][k0%2]);
while (k0 != 1) {
int bef = last[n][k0];
printf("%d ", bef);
n = bef; k0--;
}
// cout << (clock() - c) / (double)CLOCKS_PER_SEC;
}
Compilation message (stderr)
sequence.cpp: In function 'int main()':
sequence.cpp:52:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int n, k0; scanf("%d %d", &n, &k0);
^
sequence.cpp:54:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i]);
^
# | 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... |