Submission #1151377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151377		AlgorithmWarrior	Split the sequence (APIO14_sequence)	C++20	100 / 100	646 ms	83176 KiB

sequence

#pragma GCC optimize ("03,unroll-loops")
#include <bits/stdc++.h>

using namespace std;

int const MAX=1e5+5;
long long dp[MAX][2];
int ult[MAX][205];
long long sp[MAX];
int n,k;

void read(){
    cin>>n>>k;
    ++k;
    int i;
    for(i=1;i<=n;++i){
        cin>>sp[i];
        sp[i]+=sp[i-1];
    }
}

long long aa(int i){
    return sp[i];
}

long long bb(int i,int dim){
    return dp[i][dim]-sp[i]*sp[i];
}

double inters(int i,int j,int dim){
    return 1.0*(bb(j,dim)-bb(i,dim))/(aa(i)-aa(j));
}

void get_dp(){
    int i,j;
    for(j=2;j<=k;++j){
        deque<int>deq;
        deq.push_back(j-1);
        int nou=(j&1);
        int vechi=1-nou;
        for(i=j;i<=n;++i){
            while(deq.size()>1 && inters(deq[0],deq[1],vechi)<=1.0*sp[i])
                deq.pop_front();
            int ind=deq[0];
            dp[i][nou]=bb(ind,vechi)+aa(ind)*sp[i];
            ult[i][j]=ind;
            if(sp[deq.back()]==sp[i]){
                ind=deq.back();
                if(bb(i,vechi)<=bb(ind,vechi))
                    continue;
                deq.pop_back();
            }
            while(deq.size()>1 && inters(deq.back(),deq[deq.size()-2],vechi)>=inters(i,deq.back(),vechi))
                deq.pop_back();
            deq.push_back(i);
        }
    }
}

void write(){
    cout<<dp[n][k&1]<<'\n';
    stack<int>stv;
    int i;
    int ind=n;
    for(i=k;i>1;--i){
        ind=ult[ind][i];
        stv.push(ind);
    }
    while(!stv.empty()){
        cout<<stv.top()<<' ';
        stv.pop();
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    read();
    get_dp();
    write();
    return 0;
}

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