Submission #1026996

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026996		borisAngelov	Split the sequence (APIO14_sequence)	C++17	50 / 100	2036 ms	60808 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

const int maxn = 10005;
const int maxk = 205;
const long long inf = 1e18;

int n, k;
long long a[maxn];
long long pref[maxn];

long long dp[maxn][maxk];
int prvState[maxn][maxn];

long long sum(int from, int to)
{
    return pref[to] - pref[from - 1];
}

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> k;

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        pref[i] = pref[i - 1] + a[i];
    }

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= min(i - 1, k); ++j)
        {
            dp[i][j] = -inf;
            prvState[i][j] = -1;

            for (int prv = i - 1; prv >= 1; --prv)
            {
                long long curr = dp[prv][j - 1] + sum(1, prv) * sum(prv + 1, i);

                if (dp[i][j] < curr)
                {
                    dp[i][j] = curr;
                    prvState[i][j] = prv;
                }
            }
        }
    }

    stack<int> splits;
    int pos = n;
    long long ans = dp[n][k];

    while (k > 0)
    {
        splits.push(prvState[pos][k]);
        pos = splits.top();
        --k;
    }

    cout << ans << endl;

    while (!splits.empty())
    {
        cout << splits.top() << " ";
        splits.pop();
    }

    cout << endl;

    return 0;
}

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

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