제출 #1272286

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272286		pvb.tunglam	수열 (APIO14_sequence)	C++20	0 / 100	2 ms	1848 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int N, K;
ll a[100009], pre[100009];
ll dp_prev[100009], dp_cur[100009];
int par[100009][205]; // lưu cut để truy vết

struct Line {
    ll m, b;
    int idx;
};

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();
            // kiểm tra l có cần xóa l2
            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++) dp_prev[i] = -1e18; // -oo
    dp_prev[0] = 0;

    for(int j = 1; j <= K; j++) {
        CHT cht;
        for(int i=0;i<=N;i++) dp_cur[i] = -1e18;
        cht.add(0,0,0); // k=0
        for(int i = 1; i <= N; i++) {
            auto [val,k] = cht.query(pre[i]);
            dp_cur[i] = val;
            par[i][j] = k;
            cht.add(pre[i], dp_prev[i]-pre[i]*pre[i], i);
        }
        swap(dp_prev, dp_cur);
    }

    cout << dp_prev[N] << "\n";

    // truy vết cut
    vector<int> cuts;
    int ci = N, cj = K;
    while(cj > 0) {
        int t = par[ci][cj];
        if (t <= 0) break; // đã đến đầu
        cuts.push_back(t);
        ci = t;
        --cj;
    }
    reverse(cuts.begin(), cuts.end());

    // luôn in 1 dòng
    for(size_t i=0;i<cuts.size();i++) {
        if(i) cout << " ";
        cout << cuts[i];
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    solve();
}

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