Submission #636859

#	Time	Username	Problem	Language	Result	Execution time	Memory
636859		elkernos	Split the sequence (APIO14_sequence)	C++17	100 / 100	478 ms	87572 KiB

sequence

#include <bits/stdc++.h>

using namespace std;
#define int long long

struct L {
    int a, b, from;
    int operator()(int x) { return a * x + b; }
    pair<int, int> inter(L &he) const
    {
        int up = he.b - b;
        int down = a - he.a;
        return {up, down};
    }
};

struct CHT {
    vector<L> hull;
    int start = 0;
    pair<int, int> query(int x, int i)
    {
        while(start <= (int)hull.size() - 2) {
            L A = hull[start], B = hull[start + 1];
            if(B.from < i && A(x) <= B(x))
                start++;
            else
                break;
        }
        return {hull[start](x), hull[start].from};
    }
    void add(L x)
    {
        if(!hull.empty() && hull.back().a == x.a) {
            if(hull.back().b < x.b) {
                hull.pop_back();
            }
            else {
                return;
            }
        }
        while(start <= (int)hull.size() - 2) {
            L A = hull.end()[-2], B = hull.end()[-1];
            auto one = A.inter(B), two = B.inter(x);
            assert(one.second && two.second);
            if(one.first * two.second > two.first * one.second) {
                hull.pop_back();
            }
            else {
                break;
            }
        }
        hull.push_back(x);
    }
};

int sq(int x) { return x * x; }

int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, k;
    cin >> n >> k;
    vector<int> p(n + 1);
    for(int i = 1; i <= n; i++) {
        cin >> p[i];
        p[i] += p[i - 1];
    }
    CHT dp;
    for(int i = 1; i <= n; i++) {
        dp.add({p[i], -sq(p[i]), i});
    }
    vector<vector<int32_t>> come(k + 1, vector<int32_t>(n + 1));
    for(int now = 1; now <= k; now++) {
        CHT new_dp;
        for(int i = now + 1; i <= n; i++) {
            auto in = dp.query(p[i], i);
            if(now == k && i == n) {
                cout << in.first << '\n';
            }
            come[now][i] = in.second;
            if(i < n) {
                new_dp.add({p[i], in.first - sq(p[i]), i});
            }
        }
        dp = new_dp;
    }
    vector<int> print(k);
    int nn = n, kk = k;
    while(kk) {
        nn = come[kk][nn];
        kk--;
        print[kk] = nn;
    }
    for(int i = 0; i < k; i++) {
        cout << print[i] << " ";
    }
    cout << '\n';
}

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