제출 #1272282

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272282		pvb.tunglam	수열 (APIO14_sequence)	C++20	0 / 100	1 ms	1848 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 = 1e18;

/*------------- I alone decide my fate ! -------------*/

int N, K;
ll a[100009], pre[100009];
ll dp_prev[100009], dp_cur[100009];
int par[100009][205]; // lưu cut cho từng j

// Convex Hull Trick - maximum
struct Line {
    ll m, b;
    int idx; // vị trí cut
};
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();
            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];
	}

	// khởi tạo dp_prev
	for(int i=0;i<=N;i++) dp_prev[i] = -oo;
	dp_prev[0] = 0;

	// DP theo số cut
	for(int j = 1; j <= K; j++) {
		CHT cht;
		for(int i=0;i<=N;i++) dp_cur[i] = -oo;
		cht.add(0, 0, 0); // dòng đầu tiên, k=0
		for(int i = 1; i <= N; i++) {
			auto [val, k] = cht.query(pre[i]);
			dp_cur[i] = val;
			par[i][j] = k; // lưu cut để truy vết
			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;
		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();
}

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