Submission #732789

#	Time	Username	Problem	Language	Result	Execution time	Memory
732789		cologne	Split the sequence (APIO14_sequence)	C++17	100 / 100	667 ms	84612 KiB

sequence

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

struct Line
{
    long a, b;
    int idx;
};
long double isect(Line v1, Line v2)
{
    auto [a1, b1, i1] = v1;
    auto [a2, b2, i2] = v2;
    return (b2 - b1) / (long double)(a1 - a2);
}
long eval(Line v, long x)
{
    auto [a, b, i] = v;
    return a * x + b;
}
struct CHT
{
    deque<Line> lines;
    // insert ax+b line, a should be increasing
    void push_line(Line l)
    {
        if (lines.empty())
            lines.push_back(l);
        if (lines.back().a == l.a && lines.back().b >= l.b)
        {
            lines.back() = l;
            return;
        }
        while (lines.size() >= 2 &&
               isect(*lines.rbegin(), *next(lines.rbegin())) >= isect(*lines.rbegin(), l))
            lines.pop_back();
        lines.push_back(l);
    }

    // queries x, find max(ax+b) x should be increasing
    pair<long, int> query(long x)
    {
        while (lines.size() >= 2 &&
               eval(*lines.begin(), x) <= eval(*next(lines.begin()), x))
            lines.pop_front();
        return make_pair(eval(*lines.begin(), x), lines.begin()->idx);
    }
};

pair<long, vector<int>> solve(vector<long> A, int K)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N = A.size();
    vector<long> S(N + 1);
    vector<long> pD(N + 1);
    vector<vector<int>> bktk(K + 1, vector<int>(N + 1));
    for (int i = 0; i < N; ++i)
        S[i + 1] = S[i] + A[i];

    for (int k = 1; k <= K; ++k)
    {
        CHT cht;
        vector<long> D(N + 1);
        cht.push_line({S[N], 0L, 0});
        for (int i = 1; i <= N; ++i)
        {
            auto [v, q] = cht.query(S[i]);
            bktk[k][i] = q;
            D[i] = -S[i] * S[i] + v;
            cht.push_line({S[N] + S[i],
                           pD[i] - S[i] * S[N],
                           i});
        }
        pD = D;
    }

    int cur = pD.rend() - max_element(next(pD.rbegin()), pD.rend()) - 1;
    long ans = pD[cur];
    vector<int> ret(K);
    for (int k = K; k >= 1; --k)
    {
        ret[k - 1] = cur;
        cur = bktk[k][cur];
    }
    return {ans, ret};
}

int main()
{
    int N, K;
    cin >> N >> K;
    vector<long> A(N);
    for (auto &x : A)
        cin >> x;
    auto [ans, res] = solve(A, K);
    cout << ans << endl;
    for (int x : res)
        cout << x << " ";
    cout << endl;
}

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