Submission #712976

#	Time	Username	Problem	Language	Result	Execution time	Memory
712976		bin9638	Split the sequence (APIO14_sequence)	C++17	0 / 100	109 ms	131072 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define N 100010
#define ii pair<int,int>
#define fs first
#define sc second
#define ld double
#define int ll

int dp[210][210][210],n,k,sum[N];

void selfmax(int&u,int v)
{
    u=max(u,v);
}

int32_t main()
{
    #ifdef SKY
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    #endif // SKY
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>sum[i],sum[i]+=sum[i-1];
    memset(dp,-0x3f3f,sizeof(dp));
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            dp[i][j][0]=0;
    for(int t=1;t<=k;t++)
        for(int l=1;l<=n;l++)
            for(int r=l;r<=n;r++)
                for(int i=l;i<=r;i++)
                    for(int c=0;c<t;c++)
                    {
                        selfmax(dp[l][r][t],dp[l][i][c]+dp[i+1][r][t-c-1]+(sum[r]-sum[i])*(sum[i]-sum[l-1]));
                      //  if(l==4&&r==7&&t==1&&i==5)cout<<(sum[r]-sum[i])*(sum[i]-sum[l-1])<<endl;
                    }
   // cout<<dp[4][7][1]<<endl;
    cout<<dp[1][n][k];
}

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