Submission #591246

#	Time	Username	Problem	Language	Result	Execution time	Memory
591246		dryeab	Split the sequence (APIO14_sequence)	C++17	0 / 100	9 ms	1612 KiB

sequence

#include <bits/stdc++.h>

using ll = long long;

using namespace std;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin >> n >> k;

    vector<ll> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        a[i] += a[i - 1];
    }

    int m, l, r;
    ll M = 0;

    for (int i = 1; i <= n; ++i) {
        if ((a[n] - a[i]) * a[i] > M) {
            m = i;
            M = (a[n] - a[i]) * a[i];
        }
    }

    priority_queue<pair<pair<ll, int>, pair<int, int>>> pq;
    pq.push({{M, m}, {1, n}});

    ll res = 0;
    vector<int> ord;

    while (k) {

        auto top = pq.top();
        pq.pop();

        M = top.first.first, m = top.first.second;
        l = top.second.first, r = top.second.second;

        ord.push_back(m); // add the divided point

        res += M;

        if (l != r) {
            M = 0;
            int m2;
            for (int i = l; i <= m; ++i) {
                if ((a[m] - a[i]) * (a[i] - a[l - 1]) > M) {
                    m2 = i;
                    M = (a[m] - a[i]) * (a[i] - a[l - 1]);
                }
            }

            pq.push({{M, m2}, {l, m}});

            M = 0;
            for (int i = m + 1; i <= r; ++i) {
                if (((a[r] - a[i]) * (a[i] - a[m])) > M) {
                    m2 = i;
                    M = (a[r] - a[i]) * (a[i] - a[m]);
                }
            }

            pq.push({{M, m2}, {m + 1, r}});
        }

        k--;
    }

    cout << res << '\n';

    for (auto x : ord)
        cout << x << " ";
}

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