Submission #876573

#	Time	Username	Problem	Language	Result	Execution time	Memory
876573		rukashii	Split the sequence (APIO14_sequence)	C++17	100 / 100	880 ms	84468 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll pref[100100];
struct line {
    ll m, c;
    int idx;
};
struct CHT {
    deque<line> dq;
    int p;
    void clear() {
        while (!dq.empty()) dq.pop_back();
        p = 0;
    }
    bool replace(line x, line y, line z) {
        return (x.c - y.c) * (z.m - x.m) >= (x.c - z.c) * (y.m - x.m);
    }
    void add(line x) {
        while (dq.size() > 1 && replace(dq[dq.size() - 2], dq.back(), x)) {
            dq.pop_back();
        }
        dq.push_back(x);
    }
    line query(ll x) {
        p = min(p, (int)dq.size() - 1);
        while (p < (int)dq.size() - 1 && dq[p].c - dq[p + 1].c < x * (dq[p + 1].m - dq[p].m)) p++;
        return dq[p];
    }
} cht;
ll dp[2][100100];
int p[202][100001];
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    k++;
    for (int i = 1;i <= n;i++) {
        int t;
        cin >> t;
        pref[i] = pref[i - 1] + t;
    }
    pref[n + 1] = pref[n];
    for (int i = 1;i <= n;i++) {
        dp[1][i] = pref[i] * (pref[n] - pref[i]);
    }
    for (int i = 2;i <= k;i++) {
        cht.clear();
        int now = i & 1, prev = 1 - now;
        cht.add({ pref[i - 1], -pref[i - 1] * pref[n] + dp[prev][i - 1] , i - 1 });
        for (int j = i;j <= n;j++) {
            line t = cht.query(pref[j]);
            dp[now][j] = t.m * pref[j] + t.c - pref[j] * pref[j] + pref[j] * pref[n];
            cht.add({ pref[j], -pref[j] * pref[n] + dp[prev][j] , j });
            p[i][j] = t.idx;
        }
    }
    int idx = p[k][n];
    ll mx = dp[k & 1][n];
    cout << mx << '\n';
    do {
        cout << idx << ' ';
        idx = p[--k][idx];
    } while (k > 1);
    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