Submission #19174

#	Time	Username	Problem	Language	Result	Execution time	Memory
19174		mindol	Split the sequence (APIO14_sequence)	C++14	100 / 100	1614 ms	83624 KiB

sequence

#include<cstdio>
#include<deque>
#include<algorithm>
#include<stack>
using namespace std;

int S[100001];
long long dp[100001][2];
int sel[100001][202];
struct pll{ long long first,second; int index; };

deque<pll> dq;
double crossX(pll p,pll q)
{
    return ((double)q.second-p.second)/((double)p.first-q.first);
}
void push(long long a,long long b,int index) // ax+b
{
    if(!dq.empty() && dq.back().first==a)
    {
        dq.back().second=max(dq.back().second,b);
        return;
    }
    dq.push_back({a,b,index});
    while(dq.size()>=3)
    {
        int sz=dq.size();
        if(crossX(dq[sz-3],dq[sz-2])>crossX(dq[sz-3],dq[sz-1]))
            dq[sz-2]=dq[sz-1], dq.pop_back();
        else break;
    }
}
pll getMax(long long x)
{
    while(dq.size()>=2)
    {
        if(dq[0].first*x+dq[0].second <= dq[1].first*x+dq[1].second)
            dq.pop_front();
        else break;
    }
    return dq[0];
}

stack<int> st;

int main()
{
    int N,K;
    scanf("%d %d",&N,&K); K++;
    for(int i=1,a;i<=N;i++)
        scanf("%d",&a), S[i]=S[i-1]+a;
    for(int j=2;j<=K;j++)
    {
        push(S[j-1],dp[j-1][(j-1)&1]-(long long)S[j-1]*S[j-1],j-1);
        for(int i=j;i<=N;i++)
        {
            pll opt=getMax(S[i]);
            dp[i][j&1]=opt.first*S[i]+opt.second;
            sel[i][j]=opt.index;
            push(S[i],dp[i][(j-1)&1]-(long long)S[i]*S[i],i);
        }
        dq.clear();
    }
    printf("%lld\n",dp[N][K&1]);
    for(int i=N,j=K;j>=2;j--)
    {
        i=sel[i][j];
        st.push(i);
    }
    while(!st.empty()) printf("%d ",st.top()), st.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