This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/**
* hello
* author: N29
* created: 2024-06-15 09:16:01
**/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define ld long double
#define y1 cheza
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N=1e5+2;
const int M=5001;
const int B=447;
const int mod=998244353;
const ll INF=1e9;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
const double eps=1e-6;
struct line{
int m,c;
int eval(int x){
return m*x+c;
}
ld inter(line l){
return (ld)(c-l.c)/(l.m-m);
}
};
int n,k;
int a[N];
int dp[202][N];
int pref[N];
deque<line>q;
bool check(line x,line y,line z){
return (z.c-x.c)*(x.m-y.m)<=(y.c-x.c)*(x.m-z.m);
}
void add(int m,int b){
line x={m,b};
while(q.size()>=2&&check(q[q.size()-2],q.back(),x)){
q.pop_back();
}
q.push_back(x);
}
int query(int x){
while(q.size()>=2&&q[0].eval(x)<=q[1].eval(x)){
q.pop_front();
}
return q.front().eval(x);
}
void test(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
pref[i]=pref[i-1]+a[i];
}
// k++;
for(int i=1;i<=k;i++){
q.clear();
for(int j=i;j<=n;j++){
// lc.add(pref[j-1],dp[i-1][j-1]-pref[j-1]*pref[j-1]);
add(pref[j-1],dp[i-1][j-1]-pref[j-1]*pref[j-1]);
dp[i][j]=query(pref[j]);
}
}
vector<int>v;
int cur=n;
for(int i=k-1;i>=0;i--){
for(int j=cur;j>=1;j--){
int d=dp[i][j-1]+pref[j-1]*(pref[cur]-pref[j-1]);
if(dp[i+1][cur]==d){
cur=j-1;
v.push_back(j-1);
break;
}
}
}
// for(int i=1;i<=k;i++){
// for(int j=1;j<=n;j++){
// cout<<dp[i][j]<<' ';
// }
// cout<<'\n';
// }
if(v.size()&&v.back()==0)v.pop_back();
cout<<dp[k][n]<<'\n';
reverse(v.begin(),v.end());
for(auto i:v){
cout<<i<<' ';
}
cout<<'\n';
}
/*
*/
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// cout.tie(nullptr);
int t2=1;
// cin>>t2;
for(int i=1;i<=t2;i++){
test();
}
}
# | 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... |