Submission #546183

#	Time	Username	Problem	Language	Result	Execution time	Memory
546183		Jomnoi	Split the sequence (APIO14_sequence)	C++17	71 / 100	2072 ms	35496 KiB

sequence

#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;

const int MAX_N = 1e5 + 10;
const int MAX_K = 2e2 + 10;
const long long INF = 9e18 + 7;

bool QueryMode;
int A[MAX_N];
int parent[MAX_K][MAX_N];
long long pre[MAX_N], dp[MAX_N];

class Line {
public :
    mutable long long m, c, p;
    mutable int idx;
    Line() : m(0), c(-INF), p(0), idx(0) {}
    Line(const long long &m_, const long long &c_, const int &i) : m(m_), c(c_), p(0), idx(i) {}
    Line(const long long &m_, const long long &c_, const int &i, const long long &p_) : m(m_), c(c_), idx(i), p(p_) {}

    bool operator<(const Line &o) const {
        if(QueryMode == true) {
            return p < o.p;
        }
        return m < o.m;
    }
};

class LineContainer : multiset <Line> {
public :
    void init() {
        clear();
    }

    long long divide(const long long &a, const long long &b) {
        return a / b - ((a ^ b) < 0 and a % b != 0);
    }

    bool intersect(iterator now, iterator nxt) {
        if(nxt == end()) {
            now->p = INF;
            return false;
        }

        if(now->m == nxt->m) {
            now->p = INF;
            if(now->c < nxt->c) {
                now->p = -INF;
            }
        }
        else {
            now->p = divide(nxt->c - now->c, now->m - nxt->m);
        }
        return now->p >= nxt->p;
    }

    void addline(const Line &f) {
        auto nxt = insert(f), now = nxt++, prv = now;
        while(intersect(now, nxt) == true) {
            nxt = erase(nxt);
        }
        if(prv != begin() and intersect(--prv, now) == true) {
            intersect(prv, now = erase(now));
        }
        while((now = prv) != begin() and (--prv)->p >= now->p) {
            intersect(prv, erase(now));
        }
    }

    pair <long long, int> query(const long long &x) {
        if(empty()) {
            return make_pair(-INF, -1);
        }

        QueryMode = true;
        auto it = *lower_bound(Line(-INF, -INF, 0, x));
        QueryMode = false;
        return make_pair(it.m * x + it.c, it.idx);
    }
}cht;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int N, K;
    cin >> N >> K;
    for(int i = 1; i <= N; i++) {
        cin >> A[i];
        pre[i] = pre[i - 1] + A[i];
    }

    for(int i = 1; i < N; i++) {
        dp[i] = (pre[N] - pre[i]) * pre[i];
        cht.addline(Line(pre[i], -pre[i] * pre[N] + dp[i], i));
    }
    for(int i = 2; i <= K; i++) {
        for(int j = i; j < N; j++) {
            auto [res, idx] = cht.query(pre[j]);
            dp[j] = res + pre[j] * pre[N] - pre[j] * pre[j];
            parent[i][j] = idx;
        }   

        cht.init();
        for(int j = i; j <= N; j++) {
            cht.addline(Line(pre[j], -pre[j] * pre[N] + dp[j], j));
        }
    }

    long long ans = -INF;
    int pos = N;
    for(int i = K; i < N; i++) {
        if(ans < dp[i]) {
            ans = dp[i];
            pos = i;
        }
    }

    stack <int> stk;
    while(K > 0) {
        stk.emplace(pos);
        pos = parent[K--][pos];
    }

    cout << ans << '\n';
    while(!stk.empty()) {
        cout << stk.top() << ' ';
        stk.pop();
    }
    return 0;
}

Compilation message (stderr)

sequence.cpp: In constructor 'Line::Line(const long long int&, const long long int&, const int&, const long long int&)':
sequence.cpp:17:17: warning: 'Line::idx' will be initialized after [-Wreorder]
   17 |     mutable int idx;
      |                 ^~~
sequence.cpp:16:29: warning:   'long long int Line::p' [-Wreorder]
   16 |     mutable long long m, c, p;
      |                             ^
sequence.cpp:20:5: warning:   when initialized here [-Wreorder]
   20 |     Line(const long long &m_, const long long &c_, const int &i, const long long &p_) : m(m_), c(c_), idx(i), p(p_) {}
      |     ^~~~

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