Submission #219294

#	Time	Username	Problem	Language	Result	Execution time	Memory
219294		ToMmyDong	Split the sequence (APIO14_sequence)	C++11	100 / 100	1072 ms	81528 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 100005;
const int MAXK = 202;

int n, k ,a[MAXN], p[MAXN];
ll dp[2][MAXN];
int tr[MAXK][MAXN];

void chmx (int &x, int y) {
    x = x > y ? x : y;
}

void tran (int i, int j, int l) {
    ll nw = dp[(l&1)^1][j] + 1LL * (p[i] - p[j]) * p[j];
    if (dp[l&1][i] <= nw) {
        tr[l][i] = j;
        dp[l&1][i] = nw;
    }
}

void solve (int nL, int nR, int tL, int tR, int kd) {
    if (nL > nR) {
        return;
    }
    if (tL == tR) {
        for (int i=nL; i<=nR; i++) {
            tran(i, tL, kd);
        }
    } else {
        int nM = (nL + nR) >> 1;
        for (int i=tL; i<=min(tR, nM-1); i++) {
            tran(nM, i, kd);
        }
        solve(nL, nM-1, tL, tr[kd][nM], kd);
        solve(nM+1, nR, tr[kd][nM], tR, kd);
    }
}

int main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;
    for (int i=1; i<=n; i++) {
        cin >> a[i];
        p[i] = a[i] + p[i-1];
    }

    for (int i=1; i<=k; i++) {
        solve(1, n, 0, n, i);
    }

    cout << dp[k&1][n] << endl;

    for (int i=k; i>=1; i--) {
        cout << tr[i][n] << " \n"[i==1];
        n = tr[i][n];
    }

    return 0;
}

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