Submission #857808

#	Time	Username	Problem	Language	Result	Execution time	Memory
857808		12345678	Split the sequence (APIO14_sequence)	C++17	33 / 100	5 ms	1124 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=2e2+5;

ll n, k, qs[nx];
ll dp[nx][nx], bk[nx][nx];

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>k;
    for (int i=1; i<=n; i++) cin>>qs[i], qs[i]+=qs[i-1];
    for (int i=0; i<nx; i++) for (int j=0; j<nx; j++) dp[i][j]=LLONG_MAX;
    dp[0][0]=0;
    for (int i=1; i<=n; i++) 
    {
        for (int j=1; j<=k+1; j++) 
        {
            for (int l=0; l<i; l++) 
            {
                if (dp[l][j-1]==LLONG_MAX) continue;
                ll nv=dp[l][j-1]+(qs[i]-qs[l])*(qs[i]-qs[l]);
                if (nv<dp[i][j]) bk[i][j]=l, dp[i][j]=nv;
            }
            //cout<<i<<' '<<j<<' '<<dp[i][j]<<' '<<bk[i][j]<<'\n';
        }
    }
    cout<<(qs[n]*qs[n]-dp[n][k+1])/2<<'\n';
    ll l=n, ly=k+1;
    while (ly>1)
    {
        l=bk[l][ly];
        ly--;
        cout<<l<<' ';
    }
}

/*
7 3
4 1 3 4 0 2 3
*/

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