Submission #516980

#	Time	Username	Problem	Language	Result	Execution time	Memory
516980		shrimb	Split the sequence (APIO14_sequence)	C++17	28 / 100	2059 ms	63444 KiB

sequence

#include"bits/stdc++.h"
using namespace std;
#define int long long
#define endl '\n'

int dp[10001][201];
int dp2[10001][201];
int best[10001][201];
int best2[10001][201];

signed main() {
    int n, k;
    cin >> n >> k;
    assert(k < n);

    int a[n];
    int pref[n];
    int suff[n];
    for (int i = 0 ; i < n ; i++) {
        cin >> a[i];
        if (i) pref[i] = pref[i-1];
        else pref[i] = 0;
        pref[i] += a[i];
    }
    for (int i = n - 1 ; i >=  0 ;i--) suff[i] = (i < n - 1 ? suff[i + 1] : 0) + a[i];
    int mx1 = 0;
    for (int j = 0 ; j < k ; j++) {
        for (int i = 0 ; i < n ; i++) {
            if (j == 0) {
                if (j == k - 1) dp[i][j] = (i < n - 1 ? suff[i + 1] : 0) * pref[i];
                else dp[i][j] = 0;
                mx1 = max(mx1, dp[i][j]);
                continue;
            }
            dp[i][j] = -1e15;
            for (int l = 0 ; l < i ; l++) {
                int prod = pref[l] * (pref[i] - pref[l]);
                int v = dp[l][j-1] + prod;
                if (j == k - 1) v += (i < n - 1 ? suff[i + 1] : 0) * pref[i];
                if (v > dp[i][j]) {
                    dp[i][j] = v;
                    best[i][j] = l;
                }
            }
            mx1 = max(mx1, dp[i][j]);
        }
    }
    int mx2 = 0;
    for (int j = 0 ; j < k ; j++) {
        for (int i = n-1 ; i >= 0 ; i--) {
            if (j == 0) {
                if (j == k - 1) {
                    dp[i][j] = suff[i] * (i ? pref[i-1] : 0);
                }
                else dp2[i][j] = 0;
                mx2 = max(mx2, dp2[i][j]);
                continue;
            }
            dp2[i][j] = -1e15;
            for (int l = n-1 ; l > i ; l--) {
                int prod = suff[l] * (suff[i] - suff[l]);
                int v = dp2[l][j-1] + prod;
                if (j == k - 1) v += suff[i] * (i ? pref[i-1] : 0);
                if (v > dp2[i][j]) {
                    dp2[i][j] = v;
                    best2[i][j] = l;
                }
            }
            mx2 = max(mx2, dp2[i][j]);
        }
    }
    // for (int i = 0 ; i < n ; i++) {
    //     for (int j = 0 ; j < k ; j++) {
    //         cout << dp2[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    if (mx2 > mx1) {swap(mx2, mx1);swap(dp, dp2);swap(best, best2);}

    int cur = 0;
    int kk = k - 1;
    for (int i = 0 ; i < n ; i++) {
        if (dp[i][kk] == mx1) cur = i;
    }
    cout << mx1 << "\n";
    vector<int> v;
    while (kk >= 0) {
        v.push_back(cur + 1);
        cur = best[cur][kk--];
    }
    reverse(v.begin(), v.end());
    for (int i : v) cout << i << " ";
}

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