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;
#define forinc(a, b, c) for(int a=b, _c=c; a<=_c; ++a)
#define fordec(a, b, c) for(int a=b, _c=c; a>=_c; --a)
#define forv(a, b) for(auto &a : b)
#define rep(i, n) forinc(i, 1, n)
#define repv(i, n) forinc(i, 0, n - 1)
#define ii pair<int,int>
#define fi first
#define se second
#define all(a) begin(a), end(a)
#define reset(f, x) memset(f, x, sizeof(f))
#define eb emplace_back
#define pb push_back
const int N=1e5+5;
long long n,a[N];
long long f[2][N];
int k;
int pre[202][N];
int top;
long long s[N],x[N];
struct line{long long x,y;int id;} li[N];
double q[N];
double G(line x,line y){return 1.0*(x.y-y.y)/(y.x-x.x);}
bool ok(line p){
if(p.x==li[top].x) return false;
if(top==1) return 1;
double x1=G(p,li[top]);
double x2=G(p,li[top-1]);
return x1>x2;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
if(fopen("input.txt", "r")) freopen("input.txt", "r", stdin);
cin>>n>>k;
forinc(i,1,n) cin>>a[i], s[i]=s[i-1]+a[i];
fordec(i,n,1) x[i]=x[i+1]+a[i];
forinc(i,1,k){
int u=i&1;
top=0;
li[++top]={s[i-1],f[u^1][i-1],i-1};
q[top]=-1e15;
forinc(j,i,n-1){
int l=1, r=top, z=0;
while(l<=r) {
int mid=l+(r-l)/2;
if(q[mid]<=-x[j+1]) z=mid, l=mid+1;
else r=mid-1;
}
f[u][j]=s[j]*x[j+1]-li[z].x*x[j+1]+li[z].y;
pre[i][j]=li[z].id;
line uu;
uu.x=s[j], uu.y=f[u^1][j], uu.id=j;
if(uu.x==li[top].x && uu.y>=li[top].y) continue;
while(top && !ok(uu)) top--;
li[++top]=uu;
if(top>1) q[top]=G(li[top],li[top-1]);
}
}
int now=0;
forinc(i,1,n-1) if(f[k&1][now]<=f[k&1][i]) now=i;
cout<<f[k&1][now]<<'\n';
vector<int> ans; ans.pb(now);
fordec(i,k,2) ans.pb(pre[i][now]), now=pre[i][now];
reverse(all(ans));
forv(v, ans) cout<<v<<' ';
}
Compilation message (stderr)
sequence.cpp: In function 'int main()':
sequence.cpp:40:40: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
if(fopen("input.txt", "r")) freopen("input.txt", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |