Submission #131235

#	Time	Username	Problem	Language	Result	Execution time	Memory
131235		Minnakhmetov	Split the sequence (APIO14_sequence)	C++14	71 / 100	422 ms	131072 KiB

sequence

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

#define ll long long
#define all(aaa) aaa.begin(), aaa.end()

const ll INF = 1e18;
const int N = 1e5 + 5, K = 205;
ll dp[N][K], a[N], p[N];
int anc[N][K];

struct Line {
    ll k, b;

    int pos;

    bool q = false;
    double lx;

    bool operator < (const Line &oth) const {
        if (q)
            return k < oth.lx;
        if (oth.q)
            return lx < oth.k;
        return k > oth.k;
    }
};

struct CHT : vector<Line> {
    bool bad(iterator y) {
        iterator x, z;

        if (y != begin()) {
            x = prev(y);
            if (x->k == y->k)
                return x->b <= y->b;
        }
        if (next(y) != end()) {
            z = next(y);
            if (y->k == z->k)
                return y->k > z->k;
        }

        if (y == begin() || next(y) == end())
            return false;

        return (x->b - y->b) * 1.0 * (z->k - y->k) >= 
            (y->b - z->b) * 1.0 * (y->k - x->k);
    }

    void calcLx(iterator y) {
        if (y == begin()) {
            y->lx = -INF;
        }
        else {
            auto x = prev(y);
            y->lx = (x->b - y->b) / (double)(y->k - x->k);
        }
    }

    void add(Line a) {
        push_back(a);
        if (bad(prev(end()))) {
            pop_back();
            return;
        }
        while (size() > 1 && bad(end() - 2)) {
            erase(end() - 2);
        }
        calcLx(prev(end()));
    }

    int que(ll x) {
        auto it = upper_bound(begin(), end(), Line{x, -1, -1, 1});
        it--;
        return it->pos;
    }
} cht[K];

signed main() {
#ifdef HOME
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, k;
    cin >> n >> k;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        p[i + 1] = a[i] + p[i];
    }

    k++;

    cht[0].add({0, 0, 0});

    for (int i = 1; i <= n; i++) {
        for (int j = k; j > 0; j--) {
            if (cht[j - 1].empty())
                continue;

            int x = cht[j - 1].que(p[i]);

            

            dp[i][j] = dp[x][j - 1] + (p[i] - p[x]) * (p[i] - p[x]);
            anc[i][j] = x;
            cht[j].add({-2 * p[i], dp[i][j] + p[i] * p[i], i});
        }
    }

    cout << p[n] * (p[n] - 1) / 2 - (dp[n][k] - p[n]) / 2 << "\n";

    vector<int> v;
    while (anc[n][k] > 0) {
        n = anc[n][k];
        v.push_back(n);
        k--;
    }

    reverse(all(v));

    for (int i : v)
        cout << i << " ";

    return 0;
}

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