Submission #543568

#	Time	Username	Problem	Language	Result	Execution time	Memory
543568		Olympia	Split the sequence (APIO14_sequence)	C++17	0 / 100	2071 ms	12288 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;
const int64_t inf = -(1LL << 62);
struct line {
    int64_t m, b;
    mutable function<const line*() > succ;
    bool operator < (const line& rhs) const {
        if (rhs.b != inf) return m < rhs.m;
        const line* s = succ();
        if (!s) return 0;
        int64_t x = rhs.m;
        return b - s->b < (s->m - m) * x;
    }
};
struct CHT : public multiset<line> {
    bool bad(iterator y) {
        auto z = next(y);
        if (y == begin()) {
            if (z == end()) return 0;
            return y -> m == z -> m && y -> b <= z -> b;
        }
        auto x = prev(y);
        if (z == end()) return y -> m == x -> m && y -> b <= x -> b;
        return 1.0 * (x -> b - y -> b) * (z -> m - y -> m) >= 1.0 * (y -> b - z -> b) * (y -> m - x -> m);
    }
    void add(int64_t m, int64_t b) {
        auto y = insert({ m, b });
        y->succ = [ = ] { return next(y) == end() ? 0 : &*next(y); };
        if (bad(y)) {
            erase(y);
            return;
        }
        while (next(y) != end() && bad(next(y))) erase(next(y));
        while (y != begin() && bad(prev(y))) erase(prev(y));
    }
    int64_t query(int64_t x) {
        assert(!empty());
        auto l = *lower_bound((line) {x, inf});
        return l.m * x + l.b;
    }
};
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++) {
        CHT cht;
        dp[0][j] = 0;
        for (int i = 1; i < n - 1; i++) {
            cht.add(pref[i], dp[i - 1][j - 1]);
            dp[i][j] = 0;
            int64_t extra = pref[i + 1] * pref[n] - pref[i + 1] * pref[i + 1];
            for (int pre = 0; pre < i; pre++) {
                int64_t tot = dp[pre][j - 1] + pref[pre + 1] * (pref[i + 1] - pref[n]) ;
                if (tot > dp[i][j]) {
                    prev[i][j] = pre;
                }
            }
            dp[i][j] = max(cht.query(pref[i + 1] - pref[n]), (int64_t)0) + extra;
        }
    }
    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: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29