Submission #95909

#	Time	Username	Problem	Language	Result	Execution time	Memory
95909		314rate	Split the sequence (APIO14_sequence)	C++14	0 / 100	2064 ms	22216 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N=200+7;

int n,k;
int p[N];

int s(int l,int r)
{
        return p[r]-p[l-1];
}

int dp[N][N][N];
int f[N][N][N];
int split[N][N][N];

bool viz[N];

void go(int cnt,int l,int r)
{
        if(cnt>0)
        {
                cout<<split[cnt][l][r]<<" ";
                go(f[cnt][l][r],l,split[cnt][l][r]);
                go(cnt-1-f[cnt][l][r],split[cnt][l][r]+1,r);
        }
}

int main()
{
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        //freopen("input","r",stdin);
        //freopen("output","w",stdout);
        cin>>n>>k;
        for(int i=1;i<=n;i++)
        {
                int x;
                cin>>x;
                p[i]=p[i-1]+x;
        }
        int val;
        for(int cnt=1;cnt<=k;cnt++)
        {
                for(int pa=0;pa<cnt;pa++)
                {
                        int pb=cnt-1-pa;
                        for(int l=1;l<=n;l++)
                        {
                                for(int r=l;r<=n;r++)
                                {
                                        for(int k=l;k<r;k++)
                                        {
                                                val=dp[pa][l][k]+dp[pb][k+1][r]+s(l,k)*s(k+1,r);
                                                if(dp[cnt][l][r]<val)
                                                {
                                                        dp[cnt][l][r]=val;
                                                        f[cnt][l][r]=pa;
                                                        split[cnt][l][r]=k;
                                                }
                                        }
                                }
                        }
                }
        }
        cout<<dp[k][1][n]<<"\n";
        go(k,1,n);
        cout<<"\n";
        return 0;
        for(int i=1;i<=n;i++)
        {
                if(viz[i])
                {
                        cout<<i<<" ";
                }
        }
        cout<<"\n";
        return 0;
}
/**

**/

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