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>
#define N 100005
using namespace std;
typedef long long ll;
struct Line {
ll m,b;
ll get(ll x) {
return m*x+b;
}
long double cross(Line v) {
return 1LL*(b-v.b)/(v.m-m);
}
};
struct CHT {
Line vt[N];
int ind[N];
int ft=0,bk=0;
void adds(Line v, int i) {
while(bk-ft) {
if(vt[bk-1].m == v.m) {
if(v.b < vt[bk-1].b) {
i = ind[bk-1];
v.b = vt[bk-1].b;
}
--bk;
} else {
break;
}
}
while(bk-ft >= 2) {
if(vt[bk-2].cross(v) < vt[bk-2].cross(vt[bk-1])) {
--bk;
} else {
break;
}
}
ind[bk] = i;
vt[bk++] = v;
}
ll query(int x) {
if(bk==ft) {
assert(0);
}
while(bk-ft>=2) {
if(vt[ft].cross(vt[ft+1]) < x) {
++ft;
} else {
break;
}
}
return vt[ft].get(x);
}
void inits() {
ft = 0, bk = 0;
}
CHT() {}
} cht;
ll n, k, pref[N], dp[N][2];
int bt[N][205];
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k;
for(int i = 1; i <= n; i ++) {
cin >> pref[i];
pref[i] += pref[i-1];
}
ll ans = -1, ind;
for(int j = 1; j <= k; j ++) {
cht.inits();
if(j == 1) {
cht.adds({0,0},0);
}
for(int i = 1; i < j; i ++) {
swap(dp[i][0],dp[i][1]);
cht.adds({pref[i],-pref[n]*pref[i]+dp[i][0]},i);
}
for(int i = j; i <= n; i ++) {
swap(dp[i][0],dp[i][1]);
dp[i][1] = cht.query(pref[i])+pref[n]*pref[i]-pref[i]*pref[i];
bt[i][j] = cht.ind[cht.ft];
if(j == k && ans < dp[i][1]) {
ind = i;
ans = dp[i][1];
}
if(j > 1) {
cht.adds({pref[i],-pref[n]*pref[i]+dp[i][0]},i);
}
}
}
assert(ind >= k);
assert(ans != -1);
vector<int> pt;
int K = k;
while(ind) {
pt.push_back(ind);
ind = bt[ind][K--];
}
if(K) {
assert(k == n-1);
}
cout << ans << "\n";
sort(pt.begin(),pt.end());
for(int i: pt) cout << 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... |