Submission #1133481

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133481		totoro	Split the sequence (APIO14_sequence)	C++20	0 / 100	0 ms	324 KiB

sequence

#include <iostream>
// #include <utility>
#include <vector>

#define V std::vector

const long long NEGINFINITY = -100000000000000ll;

int main() {
    int n, k;
    std::cin >> n >> k;
    std::vector<int> v(n);
    for (int i = 0; i < n; ++i) std::cin >> v[i];
    std::vector<long long> p(n + 1);
    for (int i = 1; i <= n; ++i) p[i] = p[i - 1] + v[i - 1];
    // dp[i][kk][prev] = max score in prefix i with kk more splits, the last of which is at prev
    V<V<V<long long>>> dp(n, V<V<long long>>(k + 1));
    V<V<int>> bestfrom(n, V<int>(k + 1));
    dp[0][0].push_back(0);
    bestfrom[0][0] = -1;
    for (int kk = 1; kk <= k; ++kk) dp[0][kk].push_back(NEGINFINITY);
    for (int i = 1; i < n; ++i) {
        for (int kk = 0; kk <= std::min(k, i); ++kk) dp[i][kk].resize(i + 1);
        for (int prev = 0; prev < i; ++prev) {
            for (int kk = 0; kk <= std::min(k, i); ++kk) {
                if (kk != i)
                    dp[i][kk][prev] = dp[i - 1][kk][prev];
            }
        }
        for (int kk = 0; kk <= std::min(k, i); ++kk) {
            if (kk == 0) {
                dp[i][kk][i] = NEGINFINITY;
                continue;
            }
            long long max = NEGINFINITY;
            for (int prev = 0; prev < i; ++prev) {
                long long score = dp[i - 1][kk - 1][prev] + (p[i] - p[prev]) * (p.back() - p[i]);
                if (score > max) {
                    max = score;
                    bestfrom[i][kk] = prev;
                }
            }
            dp[i][kk][i] = max;
        }
    }

    long long max = 0;
    int cur;
    for (int prev = 0; prev < n; ++prev) {
        if (dp[n - 1][k][prev] > max) {
            max = dp[n - 1][k][prev];
            cur = prev;
        }
    }

    std::cout << max << '\n';
    int kk = k;
    while (kk) {
        std::cout << cur << " \n"[kk == 1];
        cur = bestfrom[cur][kk];
        --kk;
    }

    return 0;
}

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