Submission #321278

#	Time	Username	Problem	Language	Result	Execution time	Memory
321278		shart23	Split the sequence (APIO14_sequence)	C++14	71 / 100	349 ms	131076 KiB

sequence

#include <bits/stdc++.h>

#define int long long
#define double long double
#define all(x) x.begin(), x.end()

using namespace std;

struct Line {
    int k;
    int b;

    Line(int k_, int b_) : k(k_), b(b_) {}
};

struct CHT {
    const int INF = (int) 1e18;
    vector<Line> lns;
    vector<double> pts = {(double) -INF};
    vector<int> inds;

    double inter(Line ln1, Line ln2) {
        double x = (ln2.b - ln1.b) / (double) (ln1.k - ln2.k);
        return x;
    }

    void add(int k, int b, int ind) {
        Line nln(k, b);
        while ((int) lns.size() > 1) {
            if (k == lns.back().k) {
                if (b < lns.back().b) {
                    return;
                }
                lns.pop_back();
                inds.pop_back();
                pts.pop_back();
                continue;
            }
            double nx = inter(nln, lns[(int) lns.size() - 2]);
            if (nx < pts.back()) {
                lns.pop_back();
                inds.pop_back();
                pts.pop_back();
            } else {
                break;
            }
        }
        if (!lns.empty() && lns.back().k == k) {
            if (b < lns.back().b) {
                return;
            }
            lns.pop_back();
            inds.pop_back();
            lns.push_back(nln);
            inds.push_back(ind);
        } else {
            lns.push_back(nln);
            inds.push_back(ind);
            if ((int) lns.size() > 1) {
                pts.push_back(inter(lns.back(), lns[(int) lns.size() - 2]));
            }
        }

    }

    pair<int, int> best(int x) {
        int l = 0, r = pts.size();
        while (r - l > 1) {
            int m = (l + r) / 2;
            if (pts[m] > x) {
                r = m;
            } else {
                l = m;
            }
        }
        return {lns[l].k * x + lns[l].b, inds[l]};
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] += a[i - 1];
    }
    vector<vector<int>> dp(k + 1, vector<int>(n + 1, 0));
    vector<vector<int>> prev(k + 1, vector<int>(n + 1, -1));
    dp[0][0] = 0;
    for (int j = 1; j <= k; j++) {
        CHT cht;
        cht.add(a[j - 1], dp[j - 1][j - 1] - a[j - 1] * a[j - 1], j - 1);
        dp[j][0] = 0;
        for (int i = j; i <= n; i++) {
            auto res = cht.best(a[i]);
            dp[j][i] = res.first;
            prev[j][i] = res.second;
            cht.add(a[i], dp[j - 1][i] - a[i] * a[i], i);
        }
    }
    int ans = dp[k][n];
    cout << ans << '\n';
    vector<int> path;
    int now = n;
    for (int i = k; i >= 1; i--) {
        now = prev[i][now];
        path.push_back(now);
    }
    reverse(all(path));
    for (int el : path) {
        cout << el << ' ';
    }
    cout << '\n';
}
/*
7 3
4 1 3 4 0 2 3
 */

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