Submission #736103

#	Time	Username	Problem	Language	Result	Execution time	Memory
736103		Desh03	Split the sequence (APIO14_sequence)	C++17	100 / 100	791 ms	91764 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;
    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);
    }

    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);
    }
} cht[201];
int pre[100001], par[201][100001];
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    long long ans;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> pre[i], pre[i] += pre[i - 1];
    for (int i = 1; i <= n; i++) {
        long long prev = 0;
        for (int j = 1; j <= min(k, i - 1); j++) {
            auto [x, y] = cht[j].query(pre[i]);
            if (i == n && j == k) ans = x;
            par[j][i] = y;
            cht[j].push_line({pre[i], prev - (long long) pre[i] * pre[i], i});
            prev = x;
        }
        if (k >= i) cht[i].push_line({pre[i], prev - (long long) pre[i] * pre[i], i});
    }
    cout << ans << '\n';
    for (int x = par[k][n], i = k; i >= 1; i--, x = par[i][x])
        cout << x << ' ';
}

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