Submission #65733

#	Time	Username	Problem	Language	Result	Execution time	Memory
65733		Vahan	Split the sequence (APIO14_sequence)	C++17	71 / 100	2063 ms	120632 KiB

sequence

#include<iostream>
#include<deque>
#include<fstream>
using namespace std;
ifstream fin("./sequence/53");
long long d[100007][205],n,k,a[200000],A[200000],opt[100007][205];
long long i,j,cur;
deque<pair<long long,long long> > q;
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++)
    {
        for(i=j+1;i<=n;i++)
        {
            for(int cur=max(opt[i][j-1],max(opt[i-1][j],j));cur<=i;cur++)
            {
                if((A[i]-A[cur])*A[cur]+d[cur][j-1]>=d[i][j])
                {
                    d[i][j] = (A[i]-A[cur])*A[cur]+d[cur][j-1];
                    opt[i][j]=cur;
                }
            }
        }
    }
    cout<<d[n][k]<<endl;
    long long 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: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 0 / 29