Submission #857824

#	Time	Username	Problem	Language	Result	Execution time	Memory
857824		12345678	Split the sequence (APIO14_sequence)	C++17	100 / 100	1226 ms	84944 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int kx=2e2+5, nx=1e5+5;

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

void solve(int l, int r, int optl, int optr, int layer)
{
    if (l>r) return;
    int md=(l+r)/2, c=layer%2, pv=1-c;
    pair<ll, ll> p={LLONG_MAX, 0};
    for (int i=optl; i<=min(optr, md-1); i++) if (dp[pv][i]!=LLONG_MAX) p=min(p, {dp[pv][i]+(qs[md]-qs[i])*(qs[md]-qs[i]), i});
    dp[c][md]=p.first;
    bk[layer][md]=p.second;
    solve(l, md-1, optl, p.second, layer);
    solve(md+1, r, p.second, optr, layer);
}

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<2; i++) for (int j=0; j<nx; j++) dp[i][j]=LLONG_MAX;
    dp[0][0]=0;
    for (int i=1; i<=k+1; i++) 
    {
        for (int j=0; j<nx; j++) dp[i%2][j]=LLONG_MAX;
        solve(1, n, 0, n, i);
    }
    cout<<(qs[n]*qs[n]-dp[(k+1)%2][n])/2<<'\n';
    ll l=n, ly=k+1;
    while (ly>1)
    {
        l=bk[ly][l];
        ly--;
        cout<<l<<' ';
    }
}

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