Submission #655270

#	Time	Username	Problem	Language	Result	Execution time	Memory
655270		benjaminkleyn	Split the sequence (APIO14_sequence)	C++17	28 / 100	2096 ms	74692 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int N, K, a[100001];
ll pref[100001] = {0};
ll dp[100001][201];
int last_split[100001][201];

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

    for (int k = 1; k <= K; k++)
        for (int i = 1; i <= N; i++)
        {
            dp[i][k] = 0;
            for (int j = 0; j < i; j++)
                if (dp[j][k-1]+pref[j]*(pref[i]-pref[j])>dp[i][k])
                {
                    dp[i][k] = dp[j][k-1] + pref[j] * (pref[i] - pref[j]);
                    last_split[i][k] = j;
                }
        }

    cout << dp[N][K] << '\n';

    int i = N;
    do
    {
        i = last_split[i][K--];
        cout << i << ' ';
    } while (last_split[i][K] > 0);
    cout << '\n';

    return 0;
}

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