#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;
int n,k;
ll sq(ll a)
{
return a*a;
}
void add(ll a,ll b,ll ex,ll p,ll i)
{
ll c = l[p][0],d = l[p][1],e = l[p][2],lp = l[p][3],rp = l[p][4],ci = l[p][7];
if(a * (lp+rp)/2 + b < c * (lp+rp)/2 + d)
{
l[p][0] = a;
l[p][1] = b;
l[p][2] = ex;
l[p][7] = i;
i = ci;
a = c;
b = d;
ex = e;
}
if(a * lp + b < l[p][0] * lp + l[p][1])
{
if(lp <= (lp+rp)/2 -1)
{
if(l[p][5] != -1)
{
add(a,b,ex,l[p][5],i);
}
else
{
l[p][5] = l.size();
l.pb({a,b,ex,lp,(lp+rp)/2-1,-1,-1,i});
}
}
}
else
{
if(rp >= (lp+rp)/2 + 1)
{
if(l[p][6] != -1)
{
add(a,b,ex,l[p][6],i);
}
else
{
l[p][6] = l.size();
l.pb({a,b,ex,(lp+rp)/2+1,rp,-1,-1,i});
}
}
}
}
vector<ll> check(ll v,int p)
{
vector<ll> ans;
ans = {l[p][0] * v + l[p][1],l[p][2],l[p][7]};
if((l[p][3]+l[p][4])/2 < v && l[p][6] != -1)
{
vector<ll> c = check(v,l[p][6]);
if(c[0] < ans[0])
{
ans = c;
}
}
else if((l[p][3]+l[p][4])/2 > v && l[p][5] != -1)
{
vector<ll> c = check(v,l[p][5]);
if(c[0] < ans[0])
{
ans = c;
}
}
return ans;
}
ll pref[100000];
vector<int> ord;
pair<ll,ll> solve(ll c)
{
l.clear();
ord.clear();
l.pb({0,0,0,0,inf,-1,-1,-1});
vector<vector<ll>> ans(n);
rep(i,n)
{
ans[i] = {check(pref[i],0)[0] + pref[i]*pref[i] + c, check(pref[i],0)[1]+1,check(pref[i],0)[2]};
add(-2 * pref[i],ans[i][0] + pref[i]*pref[i],ans[i][1],0,i);
}
int i = n-1;
while(i != -1)
{
ord.pb(i);
i = ans[i][2];
}
return {ans[n-1][0] - c*ans[n-1][1],ans[n-1][1]-1};
}
int32_t main()
{
cin>>n>>k;
int cu;
cin>>cu;
pref[0] = cu;
for(int i = 1;i<n;i++)
{
int c;
cin>>c;
pref[i] = pref[i-1]+c;
}
ll l = -1;
ll r = 1e18;
pair<ll,ll> ans;
bool lc;
while(l+1 < r)
{
ll mid = (l+r)/2;
pair<ll,ll> c = solve(mid);
ans = c;
if(c.nd < k)
{
r = mid;
lc = 1;
}
else if(c.nd > k)
{
l = mid;
lc = 0;
}
else
{
break;
}
}
ll cm;
if(lc)
{
cm = r;
}
else
{
cm = l;
}
ll tans = ans.st + (k-ans.nd)*cm;
cout<<(pref[n-1]*pref[n-1]- tans)/2<<"\n";
//cout<<n<<" "<<k<<"\n";
set<int> o;
o.insert(-1);
rep(i,ord.size())
{
o.insert(ord[i]);
}
if(k > ans.nd)
{
rep(j,n)
{
rep(i,n)
{
if(!o.contains(i))
{
auto q = o.upper_bound(i);
int b = *q;
q--;
int a = *q;
if((a != -1 && sq(pref[b] - pref[a]) - sq(pref[b] - pref[i]) - sq(pref[i] - pref[a]) == cm) || (a == -1 && sq(pref[b]) - sq(pref[b] - pref[i]) - sq(pref[i]) == cm))
{
o.insert(i);
ans.nd++;
if(k == ans.nd)
{
break;
}
}
}
}
if(k == ans.nd) break;
}
}
else if(ans.nd > k)
{
rep(j,n)
{
rep(i,n-1)
{
if(o.contains(i))
{
auto q = o.upper_bound(i);
int b = *q;
q--;q--;
int a = *q;
if((a != -1 && sq(pref[b] - pref[a]) - sq(pref[b] - pref[i]) -sq(pref[i] - pref[a]) == cm) || (a == -1 && sq(pref[b]) - sq(pref[b] - pref[i]) - sq(pref[i]) == cm))
{
o.erase(i);
ans.nd--;
if(k == ans.nd)
{
break;
}
}
}
}
if(k == ans.nd) break;
}
}
for(int i : o)
{
if(i != -1 && i != n-1)
{
cout<<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... |