제출 #854994

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
854994		thinknoexit	Split the sequence (APIO14_sequence)	C++17	89 / 100	1012 ms	84244 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll pref[100100];
struct line {
    ll m, c, idx;
};
struct CHT {
    deque<line> dq;
    int p;
    void clear() {
        while (!dq.empty()) dq.pop_back();
        p = 0;
    }
    long double intercept(line x, line y) {
        long double ans = x.c - y.c;
        ans /= y.m - x.m;
        return ans;
    }
    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 && intercept(dq[p], dq[p + 1]) < x) p++;
        return dq[p];
    }
} cht;
ll dp[2][100100];
int p[201][100001];
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    for (int i = 1;i <= n;i++) {
        int t;
        cin >> t;
        pref[i] = pref[i - 1] + t;
    }
    /*
        dp[i][j] = max[l]( dp[i-1][l] + (pref[j] - pref[l]) * (pref[n] - pref[j]))
                 = max[l]( dp[i-1][l] + pref[j] * pref[n] - pref[l]*pref[n]
                                      - pref[j]*pref[j] + pref[l]*pref[j-1])
        m = pref[l], c = -pref[l] * pref[n] + dp[i-1][l]
        x = pref[j]
    */
    memset(dp, 0xc0, sizeof dp);
    dp[0][0] = 0;
    for (int i = 1;i <= k;i++) {
        cht.clear();
        int now = i & 1, prev = 1 - now;
        memset(dp[now], 0xc0, sizeof dp[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 = 0;
    ll mx = 0;
    for (int j = k;j < n;j++) {
        if (dp[k & 1][j] > mx) {
            mx = dp[k & 1][j];
            idx = j;
        }
    }
    cout << mx << '\n';
    stack<int> ans;
    int now = k;
    while (idx != 0) {
        ans.push(idx);
        idx = p[now--][idx];
    }
    while (!ans.empty()) {
        cout << ans.top() << ' ';
        ans.pop();
    }
    return 0;
}

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