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 long long maxn=10001;
long long n,k;
long long a[200001];
long long dp[maxn][201];
long long p[maxn];
void read()
{
cin>>n>>k;
for(long long i=1; i<=n; i++)
{
cin>>a[i];
p[i]=p[i-1]+a[i];
}
}
long long idx[maxn][201];
vector<long long> ans;
void rec(long long i,long long c)
{
if(c==0)return;
ans.push_back(idx[i][c]);
rec(idx[i][c],c-1);
}
struct line
{
long long a,b,id;//a*x + b;
line() {}
line(long long _a,long long _b,long long _id)
{
a=_a;
b=_b;
id=_id;
}
long long v(long long x)
{
return a*x+b;
}
};
deque<line> d1,d2;
double pt(line l1,line l2)
{
return (double)(l2.b-l1.b)/(double)(l1.a-l2.a);
}
void push_line(line l,deque<line>&d)
{
while(d.size()>1&&pt(l,d[d.size()-1])<=pt(l,d[d.size()-2]))d.pop_back();
d.push_back(l);
}
int curr=0;
pair<long long,long long> query(long long x,long long idq,deque<line> d)
{
int ii=0;
long long ans=-1,id=0;
for(long long i=curr; i<d.size(); i++)
{
if(d[i].id<idq&&ans<=d[i].v(x))
{
ans=d[i].v(x);
id=d[i].id;
ii=i;
}
else break;
}
curr=ii;
return {ans,id};
}
void solve()
{
for(long long i=1; i<=n; i++)
push_line({p[i],-p[i]*p[i],i},d1);
for(long long j=1; j<=k; j++)
{
curr=0;
//cout<<"! "<<j<<endl;
for(long long i=1; i<=n; i++)
{
pair<long long,long long> in=query(p[i],i,d1);
//cout<<i<<" "<<in.first<<" "<<in.second<<endl;
dp[i][j]=in.first;
idx[i][j]=in.second;
push_line({p[i],dp[i][j]-p[i]*p[i],i},d2);
/*for(long long l=0; l<i; l++)
{
long long curr=dp1[l][j-1]+(p[i]-p[l])*p[l];
if(dp1[i][j]<=curr)
{
dp1[i][j]=curr;
idx[i][j]=l;
}
}*/
//cout<<i<<" "<<dp1[i][j]<<endl;
}
d1=d2;
d2.clear();
}
cout<<dp[n][k]<<'\n';
rec(n,k);
sort(ans.begin(),ans.end());
for(long long i=0; i<k; i++)
cout<<ans[i]<<" ";
cout<<'\n';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
read();
solve();
return 0;
}
/*
7 3
4 1 3 4 0 2 3
10 1
1 1 0 0 0 0 0 0 0 0
*/
Compilation message (stderr)
beads.cpp: In function 'std::pair<long long int, long long int> query(long long int, long long int, std::deque<line>)':
beads.cpp:69:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for(long long i=curr; i<d.size(); 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... |