Submission #1272357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272357		pvb.tunglam	Split the sequence (APIO14_sequence)	C++20	71 / 100	80 ms	26104 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 ! -------------*/
	/* Chiec den ong sao, sao 5 canh tuoi mau... */

int N, K, a[100009];
ll dp[10009][205], pre[100009];
int par[10009][205]; 

// Convex Hull Trick - maximum
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();
            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 < 209; ++i)
		for (int j = 0; j < 205; ++j)
			par[i][j] = -1;

	for(int j = 1; j <= K; j++) {
		dp[0][j] = -oo;
	}
	dp[0][0] = 0;

	for(int j = 1; j <= K; j++) {
		CHT cht;
		cht.add(0, 0, 0); // k=0
		for(int i = 1; i <= N; i++) {
			auto [val, k] = cht.query(pre[i]);
			dp[i][j] = val;
			par[i][j] = k;
			// thêm dòng mới: y = pre[k]*x + (dp[k][j-1]-pre[k]^2)
			cht.add(pre[i], dp[i][j-1]-pre[i]*pre[i], i);
		}
	}

	cout << dp[N][K] << "\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();
}

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