Submission #712980

#	Time	Username	Problem	Language	Result	Execution time	Memory
712980		bin9638	Split the sequence (APIO14_sequence)	C++17	11 / 100	2076 ms	66948 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 n,k,sum[N];
ii dp[210][210][210];

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

void truyvet(int l,int r,int t)
{
    if(t==0)
        return;
    int mid=dp[l][r][t].sc;
    int sl=0;
    for(int c=0;c<t;c++)
        if(dp[l][mid][c].fs+dp[mid+1][r][t-c-1].fs+(sum[r]-sum[mid])*(sum[mid]-sum[l-1])==dp[l][r][t].fs)
            sl=c;
    cout<<mid<<" ";
    truyvet(l,mid,sl);
    truyvet(mid+1,r,t-sl-1);
}

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];
    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],ii{dp[l][i][c].fs+dp[i+1][r][t-c-1].fs+(sum[r]-sum[i])*(sum[i]-sum[l-1]),i});
                    }
   // cout<<dp[1][n][k].sc<<endl;
    cout<<dp[1][n][k].fs<<endl;
    truyvet(1,n,k);
}

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