| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 785961 | tosivanmak | Split the sequence (APIO14_sequence) | C++17 | 0 ms | 0 KiB |
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 ll long long
#define ld long double
struct LINE{
ld m,c,ocpt;
bool operator !=(const LINE &l)const{
return m!=l.m||c!=l.c||ocpt!=l.ocpt;
}
};
deque<LINE>q[2];
pair<ld,ld> int_pt(LINE a, LINE b){
// a.mx+a.c=b.mx+b.c
ld x=(b.c-a.c)/(a.m-b.m);
ld y=(a.m*x+a.c);
return {x,y};
}
void insert(ll id, LINE a){
while(q[id].size()>1){
// cout<<"bruh\n";
if(a.m==q[id].front().m){
if(a.c<q[id].front().c){
break;
}
else{
q[id].pop_front();
}
}
else{
if(int_pt(a,q[id].front()).first>=q[id].front().ocpt){
q[id].pop_front();
}
else{
break;
}
}
}
if(q[id].size()==0){
a.ocpt=1e18;
q[id].push_back(a);
}
else{
if(a.m!=q[id].front().m){
a.ocpt=int_pt(a,q[id].front()).first;
q[id].push_front(a);
}
else if(a.c>q[id].front().c){
q[id].pop_front();
if(q[id].size()==0){
a.ocpt=1e18;
q[id].push_front(a);
}
else{
a.ocpt=int_pt(a,q[id].front()).first;
q[id].push_front(a);
}
}
}
}
LINE qry(ll id, ld val){
ll rid=1-id;
LINE carry={-1e18,-1e18,-1e18};
LINE init={-1e18,-1e18,-1e18};
while(q[rid].size()>=1&&q[rid].back().ocpt>=val){
carry=q[rid].back();
q[rid].pop_back();
}
if(carry!=init){
q[rid].push_back(carry);
}
return q[rid].back();
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
ll n,k;
cin>>n>>k;
ll arr[n+5];
for(int i=1;i<=n;i++){
cin>>arr[i];
}
ll psum[n+5];
psum[0]=0;
for(int i=1;i<=n;i++){
psum[i]=psum[i-1]+arr[i];
}
ll dp[n+5][2];
for(int i=1;i<=n;i++){
dp[i][0]=0;
}
q[0].push_back({0,0,1e18});
for(int j=1;j<=k;j++){
ll id=j%2;
for(int i=1;i<=n-1;i++){
if(i>=j){
ll dpcut=(psum[n]-psum[i])*psum[i];
// cout<<i<<": "<<j<<": "<<dpcut<<"\n";
LINE store=qry(id,psum[n]-psum[i]);
dp[i][id]=dpcut+store.c+store.m*(psum[n]-psum[i]);
}
if(i>=j-1&&j!=1){
LINE put={(ld)-psum[i],(ld)dp[i][(1-id)],0};
insert((1-id),put);
// for(auto u: q[(1-id)]){
// cout<<u.m<<" "<<u.c<<" "<<u.ocpt<<"\n";
// }
// cout<<"\n";
}
}
q[(1-id)].clear();
// cout<<j<<": ";
// for(int i=1;i<=n-1;i++){
// cout<<dp[i][id]<<" ";
// // dp[i][(1-id)]=0;
// }
// cout<<"\n";
}
ll ck=k%2;
int ans=0;
for(int i=1;i<=n-1;i++){
ans=max(ans,dp[i][ck]);
// cout<<dp[i][ck]<<" ";
}
cout<<ans<<"\n";
}
// sum max =10^9
// dp transformation= assume nothing dp cut val + dp[op][k-1] - op[psum] * (psum[n] - cut pt)
// in cart plane, coordinate of x moves to the left
// search ocpt left
// slope= -op[psum]
// x= psum[n]-psum[i]