Submission #543571

#	Time	Username	Problem	Language	Result	Execution time	Memory
543571		Olympia	Split the sequence (APIO14_sequence)	C++17	60 / 100	546 ms	131072 KiB

sequence

#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
#include <cmath>
#include <map>
#include <random>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <limits.h>

using namespace std;
inline namespace _LineContainer {
    bool _Line_Comp_State;
    struct Line {
        mutable long long k, m, p;
        int id;
        bool operator<(const Line& o) const {
            return _Line_Comp_State ? p < o.p : k < o.k;
        }
    };

    struct LineContainer : multiset<Line> {
        long long div(long long a, long long b) { return a / b - ((a ^ b) < 0 && a % b); }

        bool isect(iterator x, iterator y) {
            if (y == end()) {
                x->p = LLONG_MAX;
                return false;
            }
            if (x->k == y->k)
                x->p = x->m > y->m ? LLONG_MAX : -LLONG_MAX;
            else
                x->p = div(y->m - x->m, x->k - y->k);
            return x->p >= y->p;
        }

        void add(long long k, long long m, int id) {
            auto z = insert({k, m, 0, id}), y = z++, x = y;
            while (isect(y, z))
                z = erase(z);
            if (x != begin() && isect(--x, y))
                isect(x, y = erase(y));
            while ((y = x) != begin() && (--x)->p >= y->p)
                isect(x, erase(y));
        }

        pair<long long, long long> query(long long x) {
            assert(!empty());
            _Line_Comp_State = 1;
            auto l = *lower_bound({0,0,x, -1});
            _Line_Comp_State = 0;
            return {l.k * x + l.m, l.id};
        }
    };
}
int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, k;
    cin >> n >> k;
    int64_t arr[n]; int64_t pref[n + 1]; pref[0] = 0;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        pref[i + 1] = pref[i] + arr[i];
    }
    int64_t dp[n - 1][k + 1];
    int64_t prev[n - 1][k + 1];
    for (int i = 0; i < n - 1; i++) {
        dp[i][1] = (pref[i + 1]) * (pref[n] - pref[i + 1]);
        prev[i][1] = -1;
    }
    for (int j = 2; j <= k; j++) {
        LineContainer cht;
        dp[0][j] = 0;
        for (int i = 1; i < n - 1; i++) {
            cht.add(pref[i], dp[i - 1][j - 1], i);
            dp[i][j] = 0;
            int64_t extra = pref[i + 1] * pref[n] - pref[i + 1] * pref[i + 1];
            dp[i][j] = max(cht.query(pref[i + 1] - pref[n]).first, 0ll) + extra;
            prev[i][j] = cht.query(pref[i + 1] - pref[n]).second - 1;
        }
    }
    int64_t myMax = 0;
    for (int i = 0; i < n - 1; i++) {
        myMax = max(myMax, dp[i][k]);
    }
    cout << myMax << '\n';
    for (int i = 0; i < n - 1; i++) {
        if (myMax == dp[i][k]) {
            int mid = i;
            int cntr = 0;
            while (cntr != k) {
                cout << mid + 1 << ' ';
                mid = prev[mid][k - cntr];
                cntr++;
            }
            return 0;
        }
    }
}

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