Submission #646231

#	Time	Username	Problem	Language	Result	Execution time	Memory
646231		Tenis0206	Split the sequence (APIO14_sequence)	C++11	50 / 100	2085 ms	36172 KiB

sequence

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int oo = INT_MAX;

int n,k;
int v[100005];

int sp[100005];

int dp[10005][205];
int l[10005][205];

int sum(int st, int dr)
{
    if(st > dr)
    {
        return 0;
    }
    return sp[dr] - sp[st - 1];
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    ++k;
    for(int i=1; i<=n; i++)
    {
        cin>>v[i];
        sp[i] = sp[i-1] + v[i];
    }
    for(int i=1; i<=n; i++)
    {
        dp[i][1] = sum(1,i) * sum(i + 1, n);
    }
    for(int j=2; j<=k; j++)
    {
        for(int i=1; i<=n; i++)
        {
            dp[i][j] = -oo;
            for(int p=i; p>=1; p--)
            {
                if(dp[p-1][j-1] + sum(p,i) * sum(i + 1, n) > dp[i][j])
                {
                    dp[i][j] = dp[p-1][j-1] + sum(p,i) * sum(i + 1, n);
                    l[i][j] = p - 1;
                }
            }
        }
    }
    cout<<dp[n][k]<<'\n';
    int poz = n;
    vector<int> rez;
    while(poz)
    {
        poz = l[poz][k--];
        if(poz)
        {
            rez.push_back(poz);
        }
    }
    reverse(rez.begin(),rez.end());
    for(auto it : rez)
    {
        cout<<it<<' ';
    }
    cout<<'\n';
    return 0;
}

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