Submission #1272364

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272364		pvb.tunglam	Split the sequence (APIO14_sequence)	C++20	100 / 100	638 ms	84632 KiB

sequence

#include <bits/stdc++.h>
#define hash _hash_
#define y1 _y1_
#define dec _dec_
using namespace std;
using ll = long long;
const ll oo = (ll)1e18;

const int MAXN = 100009;
const int MAXK = 205;

int N, K, a[MAXN];
ll pre[MAXN];
int par[MAXN][MAXK];

struct Line { ll m, b; int idx; long double interX(const Line &other) const { return (long double)(other.b - b) / (m - other.m); } };
struct CHT {
    deque<Line> dq;
    void add(ll m, ll b, int idx) {
        Line l = {m,b,idx};
        while (dq.size() >= 2) {
            auto &l1 = dq[dq.size()-2], &l2 = dq.back();
            // lưu ý: nếu test quá lớn có thể cần __int128 ở biểu thức này
            if ((l2.b - l1.b) * (l1.m - l.m) >= (l.b - l1.b) * (l1.m - l2.m)) dq.pop_back();
            else break;
        }
        dq.push_back(l);
    }
    pair<ll,int> query(ll x) {
        while (dq.size() >= 2) {
            auto &l1 = dq[0], &l2 = dq[1];
            if (l2.m * x + l2.b >= l1.m * x + l1.b) dq.pop_front();
            else break;
        }
        return {dq[0].m * x + dq[0].b, dq[0].idx};
    }
};

void solve() {
    cin >> N >> K;
    for (int i = 1; i <= N; ++i) { cin >> a[i]; pre[i] = pre[i-1] + a[i]; }
    for (int i = 0; i <= N; ++i) for (int j = 0; j <= K; ++j) par[i][j] = -1;

    // dp_prev tương ứng cột j=0 của dp gốc: dp[i][0] = 0 với mọi i (mảng global ban đầu của bạn có vậy)
    vector<ll> dp_prev(N+1, 0), dp_cur(N+1, -oo);

    for (int j = 1; j <= K; ++j) {
        CHT cht;
        // PHẢI giữ đúng như code gốc: luôn thêm (0,0,0) mỗi j
        cht.add(0, 0, 0);
        fill(dp_cur.begin(), dp_cur.end(), -oo);
        for (int i = 1; i <= N; ++i) {
            auto [val, k] = cht.query(pre[i]);
            dp_cur[i] = val;
            par[i][j] = k;
            // thêm dòng dùng dp_prev[i] == dp[i][j-1]
            cht.add(pre[i], dp_prev[i] - pre[i]*pre[i], i);
        }
        dp_prev.swap(dp_cur);
    }

    cout << dp_prev[N] << "\n";
    vector<int> cuts;
    int ci = N, cj = K;
    while (cj > 0) {
        int t = par[ci][cj];
        if (t == -1) break;
        if (t > 0) cuts.push_back(t);
        ci = t; --cj;
    }
    reverse(cuts.begin(), cuts.end());
    for (size_t i = 0; i < cuts.size(); ++i) {
        if (i) cout << " ";
        cout << cuts[i];
    }
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

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