Submission #131241

#	Time	Username	Problem	Language	Result	Execution time	Memory
131241		Minnakhmetov	Split the sequence (APIO14_sequence)	C++14	100 / 100	755 ms	85200 KiB

sequence

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

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

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

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> {
    int opt = -1;

    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);
        }
        opt = min(opt, (int)size() - 1);
        calcLx(prev(end()));
    }

    int que(ll x) {
        while (opt + 1 < size() && (begin() + opt + 1)->lx <= x)
            opt++;
        return (begin() + opt)->pos;
    }
} cht;

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++;

    for (int i = 1; i <= n; i++) {
        dp[1][i] = p[i] * p[i];
    }

    for (int i = 2; i <= k; i++) {
        cht.clear();
        cht.opt = -1;
        for (int j = i; j <= n; j++) {
            cht.add({-2 * p[j - 1], dp[(i & 1) ^ 1][j - 1] + p[j - 1] * p[j - 1], j - 1});

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

            dp[i & 1][j] = dp[(i & 1) ^ 1][x] + (p[j] - p[x]) * (p[j] - p[x]);
            anc[i][j] = x;
        }
    }

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

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

    reverse(all(v));

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

    return 0;
}

Compilation message (stderr)

sequence.cpp: In member function 'int CHT::que(long long int)':
sequence.cpp:77:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (opt + 1 < size() && (begin() + opt + 1)->lx <= 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