Submission #63049

#	Time	Username	Problem	Language	Result	Execution time	Memory
63049		Vahan	Split the sequence (APIO14_sequence)	C++17	33 / 100	1426 ms	132096 KiB

sequence

#include<iostream>
#include<deque>
using namespace std;
long long d[100007][201],n,k,a[200000],A[200000];
int i,j;
deque<int> q;
int m(int x,int y)
{
    return (A[i]-A[y])*A[y]+d[y][j-1]-(A[i]-A[x])*A[x]-d[x][j-1];
}
int main()
{
    cin>>n>>k;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
        A[i]=A[i-1]+a[i];;
    }
    for(j=1;j<=k;j++)
    {
        q.clear();
        for(i=j;i<=n;i++)
        {
            while(q.size()>=2 && m(q[0],q[1])>=0)
                q.pop_front();
            if (!q.empty())
                d[i][j] = (A[i]-A[q[0]])*A[q[0]]+d[q[0]][j-1];
            /*while (q.size() >= 2 && m(q[q.size()-2], q[q.size()-1])< m(q[q.size()-1],i))
                q.pop_back(); */
            q.push_back(i);
        }
    }
    cout<<d[n][k]<<endl;
    int l=n,r=k;
    for(i=n-1;i>=1;i--)
    {
        if((A[l]-A[i])*A[i]+d[i][r-1]==d[l][r])
        {
            cout<<i<<" ";
            r--;
            if(r==0)
                break;
            l=i;
        }
    }
    return 0;
}
/*
7 3
4 1 3 4 0 2 3*/

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