Submission #1173628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173628		ivaziva	Split the sequence (APIO14_sequence)	C++20	71 / 100	572 ms	30040 KiB

sequence

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

using namespace std;

#define MAXN 100001
#define MAXM 201
#define int long long
const int MIN = -1e9, MAX = 1e9;

struct Node {
    pair<int, int> line;
    int left, right;
    Node() : line({0, -LLONG_MAX}), left(-1), right(-1) {}
};

class LiChaoTree {
private:
    vector<Node> treeNodes;
    unordered_map<int, int> lineIndex;
    int minX, maxX;

    int get(int x, pair<int, int> line) {
        return line.first * x + line.second;
    }

    void update(int &nodeID, int l, int r, pair<int, int> line, int index) {
        if (nodeID == -1) {
            nodeID = treeNodes.size();
            treeNodes.emplace_back();
        }
        Node &node = treeNodes[nodeID];

        int mid = (l + r) / 2;
        bool leftBetter = get(l, line) > get(l, node.line);
        bool midBetter = get(mid, line) > get(mid, node.line);

        if (midBetter) swap(node.line, line);
        if (l == r) return;

        if (leftBetter != midBetter)
            update(node.left, l, mid, line, index);
        else
            update(node.right, mid + 1, r, line, index);
    }

    pair<int, int> query(int nodeID, int l, int r, int x) {
        if (nodeID == -1) return {0, -LLONG_MAX};
        Node &node = treeNodes[nodeID];

        int mid = (l + r) / 2;
        pair<int, int> bestLine = node.line;

        if (x <= mid) {
            pair<int, int> leftLine = query(node.left, l, mid, x);
            if (get(x, leftLine) > get(x, bestLine)) bestLine = leftLine;
        } else {
            pair<int, int> rightLine = query(node.right, mid + 1, r, x);
            if (get(x, rightLine) > get(x, bestLine)) bestLine = rightLine;
        }
        return bestLine;
    }

public:
    int root;
    LiChaoTree(int minX, int maxX) : root(-1), minX(minX), maxX(maxX) {
        treeNodes.reserve(MAXN * 4);
    }

    void addLine(pair<int, int> line, int index) {
        update(root, minX, maxX, line, index);
        lineIndex[line.first] = index;
    }

    int getMaxIndex(int x) {
        pair<int, int> bestLine = query(root, minX, maxX, x);
        return lineIndex.count(bestLine.first) ? lineIndex[bestLine.first] : -1;
    }

    void clear() {
        treeNodes.clear();
        lineIndex.clear();
        root = -1;
    }
};

int n, k;
int pref[MAXN], dp[2][MAXN], where[MAXM][MAXN];
LiChaoTree tree(MIN, MAX);
vector<int> ans;

int eval(pair<int, int> linija, int x) {
    return linija.first * x + linija.second;
}

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 br = 2; br <= k; br++) {
        for (int pos = br; pos < n; pos++) {
            tree.addLine({pref[pos - 1], dp[0][pos - 1] - pref[pos - 1] * pref[n]}, pos - 1);
            int bestIdx = tree.getMaxIndex(pref[pos]);
            dp[1][pos] = pref[pos] * (pref[n] - pref[pos]) + eval({pref[bestIdx], dp[0][bestIdx] - pref[bestIdx] * pref[n]}, pref[pos]);
            where[br][pos] = bestIdx;
        }
        for (int pos = br; pos < n; pos++)
            dp[0][pos] = dp[1][pos];
        tree.clear();
    }

    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 << '\n';
    ans.push_back(pos);
    for (int i = k; i >= 2; i--) {
        ans.push_back(where[i][pos]);
        pos = where[i][pos];
    }
    reverse(ans.begin(), ans.end());
    for (int x : ans) cout << x << " ";
    cout << '\n';

    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