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 int N = 2e5 + 5;
typedef long long ll;
const ll inf=1e15;
#define pb push_back
const int INF=(0x3f3f3f3f);
vector<ll>m,b,idx;
int ptr;
void add(ll _m,ll _b,ll _idx){
while(m.size()>=2){
if((b.back()-_b)*(_m-m[m.size()-2])>=(b[b.size()-2]-_b)*(_m-m.back())){
m.pop_back();
b.pop_back();
idx.pop_back();
}
else break;
}
m.pb(_m);
b.pb(_b);
idx.pb(_idx);
}
ll func(int pos,ll x){
return m[pos]*x+b[pos];
}
pair<ll,ll>get(ll x){
if(ptr>=m.size())ptr=m.size()-1;
while(ptr+1<m.size()&&func(ptr,x)<=func(ptr+1,x))ptr++;
return {func(ptr,x),idx[ptr]};
}
int path[N][305];
int x;
int K;
void print(int st,int k){
assert(x<=k);
if(path[st][k]==0){
cout<<st<<' ';
return;
}
print(path[st][k],k-1);
x++;
cout<<st<<' ';
}
ll dp[2][N];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,k;
cin>>n>>k;K=k;
ll a[n+1],pref[n+1]={};
for(int i=1;i<=n;i++){
cin>>a[i];
pref[i]=pref[i-1]+a[i];
path[i][1]=0;
}
for(int i=1;i<n;i++){
dp[1][i]=pref[i]*(pref[n]-pref[i]);
path[i][1]=0;
}
for(int i=2;i<=k;i++){
int v=(i-1)%2;
m.clear();
b.clear();
idx.clear();
ptr=0;
add(0,0,0);
for(int j=1;j<n;j++){
if(j<i){
if(j==i-1){
add(-pref[j],dp[v][j],j);
}
continue;
}
pair<ll,ll>tmp=get(pref[n]-pref[j]);
dp[v^1][j]=tmp.first+(pref[n]-pref[j])*pref[j];
path[j][i]=tmp.second;
add(-pref[j],dp[v][j],j);
}
}
ll mx=0,st=1;
for(int i=1;i<=n;i++){
if(dp[k%2][i]>mx){
mx=dp[k%2][i];
st=i;
}
}
cout<<mx<<'\n';
print(st,k);
}
Compilation message (stderr)
sequence.cpp: In function 'std::pair<long long int, long long int> get(ll)':
sequence.cpp:32:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(ptr>=m.size())ptr=m.size()-1;
~~~^~~~~~~~~~
sequence.cpp:33:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ptr+1<m.size()&&func(ptr,x)<=func(ptr+1,x))ptr++;
~~~~~^~~~~~~~~
# | 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... |