Submission #1295730

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295730		Newtonabc	Split the sequence (APIO14_sequence)	C++20	100 / 100	546 ms	82668 KiB

sequence

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
ll dp[2][N],arr[N],sum[N];
int ind[205][N];
struct CHT{
    struct line{
        ll m,c;
        double cut(line b){return (double)(b.c-c)/(double)(m-b.m);}
        ll val(ll x){return m*x+c;};
    };
    deque<pair<line,int>> hull;
    bool bad(line a,line b,line c){return c.cut(b)<=c.cut(a);}
    void ins(ll m,ll c,int i){
        line l={m,c};
        while(hull.size()>=2 && bad(hull.end()[-2].first,hull.back().first,l)) hull.pop_back();
        hull.push_back({l,i});
    }
    pair<ll,int> query(ll x){
        while(hull.size()>=2 && hull[0].first.val(x)<=hull[1].first.val(x)) hull.pop_front();
        return {hull[0].first.val(x),hull[0].second};
    }
    void clr(){while(!hull.empty()) hull.pop_back();}
}hode;
int main(){
    int n,k;
    cin>>n >>k;
    for(int i=1;i<=n;i++) cin>>arr[i];
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+arr[i];
    for(int i=1;i<=k+1;i++){
        int now=i&1;
        int pre=(i+1)&1;
        hode.ins(0,0,0);
        for(int j=1;j<=n;j++){
            pair<ll,int> ret=hode.query(sum[j]);
            if(i!=1) ind[i][j]=ret.second;
            dp[now][j]=sum[j]*(sum[n]-sum[j])+ret.first;
            if(i!=1) hode.ins(sum[j],dp[pre][j]-sum[j]*sum[n],j);
        }
        hode.clr();
    }
    cout<<dp[(k+1)&1][n] <<"\n";
    vector<int> ans;
    int now=n;
    for(int i=k+1;i>=2;i--){
        now=ind[i][now];
        ans.push_back(now);
    }
    reverse(ans.begin(),ans.end());
    for(auto tmp:ans) cout<<tmp <<" ";
}

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