Submission #459172

#	Time	Username	Problem	Language	Result	Execution time	Memory
459172		prvocislo	Split the sequence (APIO14_sequence)	C++17	100 / 100	1486 ms	80916 KiB

sequence

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
typedef long long ll;
using namespace std;

const int maxn = 1e5 + 5, maxk = 205;
ll dp[2][maxn], pf[maxn];
int split[maxk][maxn];
int n, k;
inline ll sum(const int& l, const int& r)
{
    return pf[r + 1] - pf[l];
}
void rek(int i, int l1, int l2, int r1, int r2)
// chceme zistit odpovede pre dp[i][l1] az dp[i][l2] ak optimalne splity musia lezat v intervale [r1, r2]
{
    if (l1 > l2) return;
    int mid = (l1 + l2) >> 1;
    dp[i & 1][mid] = split[i][mid] = -1;
    for (int j = max(r1, mid); j <= r2; j++)
    {
        ll val = sum(mid, j) * sum(j + 1, n - 1) + dp[(i & 1) ^ 1][j + 1];
        if (val > dp[i & 1][mid])
        {
            dp[i&1][mid] = val;
            split[i][mid] = j;
        }
    }
    rek(i, l1, mid - 1, r1, split[i][mid]);
    rek(i, mid + 1, l2, split[i][mid], r2);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 0, a; i < n; i++)
    {
        cin >> a;
        pf[i + 1] = pf[i] + a;
    }
    for (int i = 1; i <= k; i++)
    {
        for (int j = 0; j < n; j++)
        {
            dp[i & 1][j] = 0;
        }
        rek(i, 0, n - 2, 0, n - 2);
    }
    cout << dp[k & 1][0] << "\n";
    for (int i = k, j = 0; i > 0; i--)
    {
        j = split[i][j] + 1;
        cout << j << " ";
    }
    cout << "\n";
    return 0;
}

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