Submission #1279785

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279785		_filya_	Split the sequence (APIO14_sequence)	C++20	22 / 100	4 ms	1088 KiB

sequence

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

struct Line {
    mutable ll k, m, p, num;
    bool operator<(const Line& o) const { return k < o.k; }
    bool operator<(ll x) const { return p < x; }
};
struct LineContainer : multiset<Line, less<>> {
    static const ll inf = LLONG_MAX;
    ll div(ll a, ll b) {
        return a / b - ((a ^ b) < 0 && a % b); }
    bool isect(iterator x, iterator y) {
        if (y == end()) return x->p = inf, 0;
        if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
        else x->p = div(y->m - x->m, x->k - y->k);
        return x->p >= y->p;
    }
    void add(ll k, ll m, int i) {
        auto z = insert({k, m, 0, i}), y = z++, x = y;
        while (isect(y, z)) z = erase(z);
        if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
        while ((y = x) != begin() && (--x)->p >= y->p)
            isect(x, erase(y));
    }
    pair<ll, ll> query(ll x) {
        assert(!empty());
        auto l = *lower_bound(x);
        return {l.k * x + l.m, l.num};
    }
};

int main()
{
	// ifstream cin("input.txt");
    // ofstream cout("output.txt");
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, k; cin >> n >> k;
    vector<ll> a(n + 1), p(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        p[i] = p[i - 1] + a[i];
    }
    vector<vector<ll>> dp(k + 1, vector<ll>(n + 1)), opt(k + 1, vector<ll>(n + 1));
    for (int ki = 1; ki <= k; ki++) {
        LineContainer cht;
        cht.add(0, 0, 0);
        for (int i = 1; i <= n; i++) {
            auto [v, ind] = cht.query(p[i]);
            dp[ki][i] = v;
            opt[ki][i] = ind;
            cht.add(p[i], dp[ki - 1][i] - p[i] * p[i], i);
        }
    }
    cout << dp[k][n] << '\n';
    int cur = n, ki = k;
    while(cur) {
        if (opt[ki][cur]) cout << opt[ki][cur] << ' ';
        cur = opt[ki--][cur];
    }
}

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