#include <bits/stdc++.h>
#define ll int64_t
#define ld long double
using namespace std;
//
const int maxn =1e5+5;
const int mod = 1e9+7; // 998244353,1610612741
const ll inf = 1e18;
const ld pi = atan(1.0L)*4;
int n,K;
int pre[205][maxn];
ll a[maxn],s[maxn];
struct CHT{
vector<ll> M,C;
vector<int> pos;
int id=0,sz=0;
bool bad(int l1,int l2,int l3) {
return (C[l3]-C[l1])*(M[l1]-M[l2])<=(C[l2]-C[l1])*(M[l1]-M[l3]);
}
void add(ll a,ll b,int i) {
M.push_back(a);C.push_back(b);
pos.push_back(i);
sz++;
while (sz>=3&&bad(sz-3,sz-2,sz-1)){
sz--;
M.erase(M.end()-2);
C.erase(C.end()-2);
pos.erase(pos.end()-2);
}
}
pair<ll,int> get(ll x) {
if (id>=sz) id=sz-1;
while (id<sz-1&&M[id+1]*x+C[id+1]>M[id]*x+C[id]) id++;
return {M[id]*x+C[id],pos[id]};
}
};
int main() {
// freopen("../input.inp","r",stdin);
// freopen("output.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
clock_t start,end;
start=clock();
cin >>n>>K;
K++;
for (int i=1;i<=n;i++) cin >>a[i],s[i]=s[i-1]+a[i];
vector<ll> f(n+1);
for (int i=1;i<=n;i++) f[i]=s[i]*s[i];
for (int k=2;k<=K;k++) {
vector<ll> g(n+1);
CHT cht;
for (int i=k;i<=n;i++) {
cht.add(2*s[i-1],-s[i-1]*s[i-1]-f[i-1],i);
auto p=cht.get(s[i]);
g[i]=-p.first+s[i]*s[i];
pre[k][i]=p.second;
}
swap(f,g);
}
cout <<(s[n]*s[n]-f[n])/2<<'\n';
int i=n;
vector<int> v;
while (i>0) {
i=pre[K--][i]-1;
if (i>0) v.push_back(i);
}
sort(v.begin(),v.end());
for (auto i:v) cout <<i<<" ";
end=clock();
ld dur=(ld)(end-start)/(ld)(CLOCKS_PER_SEC)*(1000.0L);
cerr<<dur<<'\n';
return 0;
}
# | 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... |