Submission #515938

#	Time	Username	Problem	Language	Result	Execution time	Memory
515938		jk410	Split the sequence (APIO14_sequence)	C++17	100 / 100	731 ms	82332 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct line{
    ll a,b;
    int idx;
};
int N,K;
int Prev[201][100001];
ll A[100001],DP[2][100001];
stack<int> S;
deque<line> DQ;
ll f(line l,ll x){
    return l.a*x+l.b;
}
bool g(line l1,line l2,line l3){
    return (l1.b-l3.b)*(l2.a-l1.a)<=(l1.b-l2.b)*(l3.a-l1.a);
}
void add_line(line l){
    while ((int)DQ.size()>1&&g(DQ[(int)DQ.size()-2],DQ.back(),l))
        DQ.pop_back();
    if (!DQ.empty()&&DQ.back().a==l.a){
        if (DQ.back().b<=l.b)
            DQ.pop_back();
        else
            return;
    }
    DQ.push_back(l);
}
void query(ll x){
    while ((int)DQ.size()>1&&f(DQ[0],x)<=f(DQ[1],x))
        DQ.pop_front();
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>N>>K;
    for (int i=1; i<=N; i++){
        cin>>A[i];
        A[i]+=A[i-1];
    }
    for (int t=1; t<=K; t++){
        while (!DQ.empty())
            DQ.pop_back();
        for (int i=t+1; i<=N; i++){
            add_line({A[i-1],DP[0][i-1]-A[i-1]*A[i-1],i-1});
            query(A[i]);
            DP[1][i]=f(DQ[0],A[i]);
            Prev[t][i]=DQ[0].idx;
        }
        for (int i=t+1; i<=N; i++)
            DP[0][i]=DP[1][i];
    }
    cout<<DP[1][N]<<"\n";
    for (int t=K,i=N; t; t--){
        S.push(Prev[t][i]);
        i=Prev[t][i];
    }
    while (!S.empty()){
        cout<<S.top()<<" ";
        S.pop();
    }
    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