Submission #785962

#	Time	Username	Problem	Language	Result	Execution time	Memory
785962		tosivanmak	Split the sequence (APIO14_sequence)	C++17	0 / 100	20 ms	2588 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
#define ll int
#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;
  ll 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]

• Subtask 1: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29