Submission #1238716

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238716		sh1ft	Split the sequence (APIO14_sequence)	C++17	0 / 100	0 ms	324 KiB

sequence

/*
    author  : sh1ft
    created : 12/07/2025 21:39
    task    : APIO14_sequence
*/
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int mxN = 1e5+5, mxK = 205;

int n, k;
ll p[mxN], dp[mxK][mxN], par[mxK][mxN], q[mxK], mcm[mxK][mxK];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> p[i], p[i] += p[i-1];
    for (int i = 1; i <= n; i++) dp[0][i] = p[i];
    for (int c = 1; c <= k; c++) {
        // deque <int> cht; int sz = 0;
        // cht.emplace_back(c), sz++;
        // auto calc = [&] (int j, ll x) { return dp[c-1][j]*x - dp[c-1][j]*p[j]; };
        // auto m = [&] (int x, int y) { return (long double) (calc(x, 0) - calc(y, 0)) / (dp[c-1][y] - dp[c-1][x]); };
        // for (int i = c+1; i <= n; i++) {
        //     while (sz > 1 && calc(cht[0], p[i]) <= calc(cht[1], p[i])) cht.pop_front(), sz--;
        //     par[c][i] = cht[0];
        //     dp[c][i] = calc(cht[0], p[i]);
        //     while (sz > 1 && m(cht[sz-1], i) <= m(cht[sz-1], cht[sz-2])) cht.pop_back(), sz--;
        //     cht.emplace_back(i), sz++;
        // }

        // BRUTEFORCE
        for (int i = c+1; i <= n; i++) {
            for (int j = c; j < i; j++) {
                if (dp[c][i] < dp[c-1][j]*p[i] - dp[c-1][j]*p[j]) dp[c][i] = dp[c-1][j]*p[i] - dp[c-1][j]*p[j], par[c][i] = j;
            }
        }
    }
    vector <int> ct(k);
    int id = n;
    for (int i = k; i > 0; i--) id = par[i][id], ct[i-1] = id;
    ct.emplace_back(n), k++;
    for (int i = 1; i <= k; i++) q[i] = p[ct[i-1]];
    for (int l = 1; l+1 <= k; l++) {
        for (int i = 1; i+l <= k; i++) {
            int j = i+l;
            for (int x = i; x < j; x++) mcm[i][j] = max(mcm[i][j], mcm[i][x] + mcm[x+1][j] + (q[x] - q[i-1])*(q[j] - q[x]));
        }
    }
    cout << mcm[1][k] << '\n';
    for (int i = 0; i < k-1; i++) cout << ct[i] << ' '; cout << '\n';
}

/*
dp[c][i] = max(dp[c-1][j] * (p[i] - p[j]))
         = max(dp[c-1][j](p[i]) - dp[c-1][j]*p[j])
*/

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