제출 #855088

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
855088		thinknoexit	수열 (APIO14_sequence)	C++17	0 / 100	881 ms	83676 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;
    }
    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[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]
    */
    for (int i = 1;i <= k;i++) {
        cht.clear();
        int now = i & 1, prev = 1 - now;
        cht.add({ pref[0], -pref[0] * pref[n] + dp[prev][0] , 0 });
        for (int j = 1;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';
    do {
        cout << idx << ' ';
        idx = p[k][idx];
    } while (--k);
    return 0;
}

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