Submission #856293

#	Time	Username	Problem	Language	Result	Execution time	Memory
856293		thisistotallymyusername	Split the sequence (APIO14_sequence)	C++17	100 / 100	776 ms	85852 KiB

sequence

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;
typedef long double LD;

const int N = 100010, M = 210;

int n, k, p[N][M];
int q[N], hh, tt;
LL dp1[N], dp2[N]; // rolling array
LL s[N];

LD y(int i) {
    return dp2[i] - s[i] * s[i];
}

LD slope(int i, int j) {
    if (s[i] == s[j]) {
        return -1;
    }
    return (1.0 * y(i) - y(j)) / ((LD)s[j] - s[i]);
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        s[i] += s[i - 1];
    }
    for (int i = 1; i <= k; i++) {
        hh = tt = 0; q[hh] = 0;
        memcpy(dp2, dp1, sizeof dp2);
        for (int j = 1; j <= n; j++) {
            while (hh < tt && slope(q[hh], q[hh + 1]) <= s[j]) {
                hh++;
            }
            int t = q[hh];
            p[j][i] = t;
            dp1[j] = dp2[t] + s[t] * (s[j] - s[t]);
            while (hh < tt && slope(q[tt - 1], q[tt]) >= slope(q[tt], j)) {
                tt--;
            }
            q[++tt] = j;
        }
    }
    cout << dp1[n] << "\n";
    while (p[n][k]) {
        cout << p[n][k] << ' ';
        n = p[n][k--];
    }
    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