Submission #535187

#	Time	Username	Problem	Language	Result	Execution time	Memory
535187		ala2	Split the sequence (APIO14_sequence)	C++14	22 / 100	2074 ms	131072 KiB

sequence

#include <bits/stdc++.h>
#define int long long

using namespace std;
int n,m;
int a[1001000];
int p[1001000];
int dp[205][205][205];
int f(int i,int j,int k)
{
    if(k==0)
        return 0;
    if(i==j)
        return 0;
    if(dp[i][j][k]!=-1)
        return dp[i][j][k];
    int g=0;
    for(int ii=i; ii<j; ii++)
    {
        for(int kk=0; kk<k; kk++)
        {
            int x=p[ii]-p[i-1];
            int y=p[j]-p[ii];
            g=max(g, f(i,ii,kk)+f(ii+1,j,k-kk-1)+x*y);
        }
    }
    return dp[i][j][k]=g;
}
vector<int>v;
void d(int i,int j,int k)
{
    if(k==0)
        return ;
    if(i==j)
        return ;
    for(int ii=i; ii<j; ii++)
    {
        for(int kk=0; kk<k; kk++)
        {
            int x=p[ii]-p[i-1];
            int y=p[j]-p[ii];
         //   cout<<"     "<<f(i,ii,kk)<<"   "<<f(ii+1,j,k-kk-1)<<"  "<< x*y << "  "<<f(i,j,k)<<endl;
            if( f(i,ii,kk) + f(ii+1,j,k-kk-1) + x*y ==f(i,j,k))
            {

                v.push_back(ii);
                d(i,ii,kk);
                d(ii+1,j,k-kk-1);
                return ;

            }

        }
    }


}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    memset(dp,-1,sizeof dp);
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
        p[i]=a[i]+p[i-1];
    }
    cout<<f(1,n,m)<<endl;
    d(1,n,m);
    for(auto i:v)
        cout<<i<<" " ;


}

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