제출 #1272360

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

sequence

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

/*------------- I alone decide my fate ! -------------*/
	/* Chiec den ong sao, sao 5 canh tuoi mau... */

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

int N, K, a[MAXN];
ll pre[MAXN];
// dp hai chiều bị xoá — thay bằng 1 chiều
int par[MAXN][MAXK]; // mở đủ lớn như bạn yêu cầu

// Convex Hull Trick - maximum (CHT - Convex Hull Trick)
struct Line {
    ll m, b; // y = m*x + b
    int idx; // lưu vị trí k
    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();
            // giữ nguyên so sánh như bản gốc (chú ý overflow có thể xảy ra trong một số test cực lớn)
            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];
    }
    // init par
    for (int i = 0; i <= N; ++i)
        for (int j = 0; j <= K; ++j)
            par[i][j] = -1;

    // dp 1 chiều: dp_prev = dp[...][j-1], dp_cur = dp[...][j]
    vector<ll> dp_prev(N+1, -oo), dp_cur(N+1, -oo);
    dp_prev[0] = 0; // dp[0][0] = 0; dp[0][j>0] = -oo (sẽ tự nhiên)

    for (int j = 1; j <= K; ++j) {
        CHT cht;
        // giữ hành vi như code gốc (thêm line (0,0,0) mỗi j)
        cht.add(0, 0, 0); // tương đương k=0 theo code gốc
        // reset dp_cur
        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; // giống bản gốc: dp[i][j] = value returned
            par[i][j] = k;
            // thêm dòng mới dùng giá trị dp_prev[i] (dp[i][j-1])
            cht.add(pre[i], dp_prev[i] - pre[i]*pre[i], i);
        }
        // chuyển cột
        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";
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    solve();
    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