Submission #1173637

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173637		ivaziva	Split the sequence (APIO14_sequence)	C++20	0 / 100	3 ms	4416 KiB

sequence

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define MAXN 100001
#define MAXM 201
#define int long long
const int INF = LLONG_MAX;

struct LiChaoTree {
    struct Line {
        int m, b;
        Line(int _m = 0, int _b = -INF) : m(_m), b(_b) {}
        int eval(int x) { return m * x + b; }
    };

    vector<Line> tree;
    int minX, maxX, sz;

    LiChaoTree(int _minX, int _maxX) : minX(_minX), maxX(_maxX) {
        sz = 1;
        while (sz < (maxX - minX + 1)) sz *= 2;
        tree.assign(2 * sz, Line());
    }

    void addLine(Line newLine, int node = 1, int l = 0, int r = -1) {
        if (r == -1) r = sz - 1;
        int mid = (l + r) / 2;
        bool leftBetter = newLine.eval(l + minX) > tree[node].eval(l + minX);
        bool midBetter = newLine.eval(mid + minX) > tree[node].eval(mid + minX);
        
        if (midBetter) swap(tree[node], newLine);
        if (l == r) return;

        if (leftBetter != midBetter) addLine(newLine, 2 * node, l, mid);
        else addLine(newLine, 2 * node + 1, mid + 1, r);
    }

    int getMax(int x) {
        int pos = x - minX;
        int node = 1, l = 0, r = sz - 1;
        int best = -INF;
        
        while (true) {
            best = max(best, tree[node].eval(x));
            if (l == r) break;
            int mid = (l + r) / 2;
            if (pos <= mid) {
                node = 2 * node;
                r = mid;
            } else {
                node = 2 * node + 1;
                l = mid + 1;
            }
        }
        return best;
    }
};

int n, k;
int pref[MAXN], dp[2][MAXN];
vector<int> where[MAXM];

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;
    pref[0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> pref[i];
        pref[i] += pref[i - 1];
    }

    for (int i = 1; i < n; i++)
        dp[0][i] = pref[i] * (pref[n] - pref[i]);

    for (int i = 0; i <= k; i++) where[i].resize(n, -1);

    for (int br = 2; br <= k; br++) {
        LiChaoTree tree(0, MAXN);
        for (int pos = br; pos < n; pos++) {
            tree.addLine({pref[pos - 1], dp[0][pos - 1] - pref[pos - 1] * pref[n]});
            dp[1][pos] = pref[pos] * (pref[n] - pref[pos]) + tree.getMax(pref[pos]);
        }
        for (int pos = br; pos < n; pos++)
            dp[0][pos] = dp[1][pos];
    }

    int maks = dp[0][k], pos = k;
    for (int i = k + 1; i < n; i++) {
        if (dp[0][i] > maks) {
            maks = dp[0][i];
            pos = i;
        }
    }

    cout << maks << endl;
    return 0;
}

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