Submission #1238706

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238706		sh1ft	Split the sequence (APIO14_sequence)	C++17	11 / 100	1 ms	1096 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 = 200;

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 (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++;
        }
    }
    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: 11 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29