Submission #543551

#	Time	Username	Problem	Language	Result	Execution time	Memory
543551		Olympia	Split the sequence (APIO14_sequence)	C++17	50 / 100	2099 ms	31828 KiB

sequence

#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
#include <cmath>
#include <map>
#include <random>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <limits.h>

using namespace std;
int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, k;
    cin >> n >> k;
    int64_t arr[n]; int64_t pref[n + 1]; pref[0] = 0;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        pref[i + 1] = pref[i] + arr[i];
    }
    int64_t dp[n - 1][k + 1];
    int64_t prev[n - 1][k + 1];
    for (int i = 0; i < n - 1; i++) {
        dp[i][1] = (pref[i + 1]) * (pref[n] - pref[i + 1]);
        prev[i][1] = -1;
    }
    for (int j = 2; j <= k; j++) {
        for (int i = 0; i < n - 1; i++) {
            dp[i][j] = -1;
            for (int pre = 0; pre < i; pre++) {
                int64_t tot = dp[pre][j - 1] + (pref[i + 1] - pref[pre + 1]) * (pref[n] - pref[i + 1]);
                if (tot >= dp[i][j]) {
                    dp[i][j] = tot;
                    prev[i][j] = pre;
                }
            }
        }
    }
    int64_t myMax = 0;
    for (int i = 0; i < n - 1; i++) {
        myMax = max(myMax, dp[i][k]);
    }
    cout << myMax << '\n';
    for (int i = 0; i < n - 1; i++) {
        if (myMax == dp[i][k]) {
            int mid = i;
            int cntr = 0;
            while (cntr != k) {
                cout << mid + 1 << ' ';
                mid = prev[mid][k - cntr];
                cntr++;
            }
            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