#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define int long long
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(),a.end()
#define rep(a,b) for(int a = 0;a<b;a++)
const int inf = 1e9;
const ll infl = 1e18;
vector<vector<ll>> l[201];
int n,k;
ll sq(ll a)
{
return a*a;
}
/*void add(ll a,ll b,ll p,ll i,int c)
{
ll d = l[c][p][0],e = l[c][p][1],lp = l[c][p][2],rp = l[c][p][3],ci = l[c][p][6];
if(a * (lp+rp)/2 + b < d * (lp+rp)/2 + e)
{
l[c][p][0] = a;
l[c][p][1] = b;
l[c][p][6] = i;
i = ci;
a = d;
b = e;
}
//cerr<<a<<" "<<b<<" "<<p<<" "<<i<<" "<<c<<" "<<l[c][p][4]<<" "<<l[c][p][5]<<"\n";
if(a * lp + b < l[c][p][0] * lp + l[c][p][1])
{
if(lp <= (lp+rp)/2 -1)
{
if(l[c][p][4] != -1)
{
add(a,b,l[c][p][4],i,c);
}
else
{
l[c][p][4] = l[c].size();
l[c].pb({a,b,lp,(lp+rp)/2,-1,-1,i});
}
}
}
else
{
if(rp >= (lp+rp)/2 + 1)
{
if(l[c][p][5] != -1)
{
add(a,b,l[c][p][5],i,c);
}
else
{
l[c][p][5] = l[c].size();
l[c].pb({a,b,(lp+rp)/2+1,rp,-1,-1,i});
}
}
}
}
vector<ll> check(ll v,int p,int c)
{
vector<ll> ans;
ans = {l[c][p][0] * v + l[c][p][1],l[c][p][6]};
if((l[c][p][2]+l[c][p][3])/2 < v && l[c][p][5] != -1)
{
vector<ll> cans = check(v,l[c][p][5],c);
if(cans[0] < ans[0])
{
ans = cans;
}
}
else if((l[c][p][2]+l[c][p][3])/2 > v && l[c][p][4] != -1)
{
vector<ll> cans = check(v,l[c][p][4],c);
if(cans[0] < ans[0])
{
ans = cans;
}
}
return ans;
}*/
deque<vector<ll>> dq;
void add(ll a,ll b,int i)
{
if(dq.size() == 0)
{
dq.push_back({0,infl,a,b,i});
return;
}
vector<ll> c = dq.back();
if(c[2] == a)
{
if(c[3] > b)
{
dq.pop_back();
add(a,b,i);
}
}
else
{
ll cu = (b-c[3])/(c[2]-a) + 1;
if(cu <= c[0])
{
dq.pop_back();
add(a,b,i);
}
else
{
dq.back()[1] = cu-1;
dq.pb({cu,infl,a,b,i});
}
}
}
pair<ll,ll> check(ll c)
{
if(dq.front()[1] >=c)
{
return {c * dq.front()[2] + dq.front()[3],dq.front()[4]};
}
else
{
dq.pop_front();
return check(c);
}
}
ll pref[100000];
vector<int> ord;
ll solve()
{
vector<vector<ll>> nx;
vector<vector<ll>> nxnx;
vector<vector<pair<ll,ll>>> ans(k);
rep(q,k)
{
ans[q].resize(n-1);
nx = nxnx;
nxnx.clear();
dq.clear();
add(0,inf,-1);
if(q == 0)
{
add(0,0,-1);
}
rep(i,n-1)
{
//cout<<i<<"\n";
ans[q][i] = {check(pref[i]).st + pref[i]*pref[i],check(pref[i]).nd};
//cerr<<q<<" "<<i<<" "<<ans[q][i].st<<" "<<ans[q][i].nd<<"\n";
nxnx.pb({-2 * pref[i],ans[q][i].st + pref[i]*pref[i],i});
if(q != 0) add(nx[i][0],nx[i][1],nx[i][2]);
//cout<<ans[i][j][0]<<" "<<ans[i][j][1]<<" "<<i<<" "<<j<<"\n";
//cout<<-2*pref[i]<<" "<<ans[i][j][0] +pref[i]*pref[i]<<"\n";
}
}
//cout<<'a'<<"\n";
dq.clear();
rep(i,n-1)
{
add(nxnx[i][0],nxnx[i][1],nxnx[i][2]);
}
int ci = check(pref[n-1]).nd;
int cu = k-1;
while(ci != -1)
{
// cout<<ci<<"\n";
ord.pb(ci);
ci = ans[cu][ci].nd;
cu--;
}
reverse(all(ord));
return check(pref[n-1]).st + pref[n-1]*pref[n-1];
}
int32_t main()
{
cin>>n>>k;
int cu;
cin>>cu;
pref[0] = cu;
rep(i,n-1)
{
int c;
cin>>c;
pref[i+1] = pref[i]+c;
}
ll ans = solve();
//cerr<<ans<<"\n";
cout<<(sq(pref[n-1])-ans)/2<<"\n";
rep(i,k)
{
cout<<ord[i]+1<<" ";
}
cout<<"\n";
}
# | 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... |