Submission #312445

#	Time	Username	Problem	Language	Result	Execution time	Memory
312445		vuhoanggiap	Split the sequence (APIO14_sequence)	C++17	33 / 100	276 ms	131076 KiB

sequence

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
using namespace std; 
typedef pair<int, int> ii; 
typedef pair<ii, int> pii;  // Line + id 

int n, k; 
int a[100005], pre[100005]; 

int dp[205][100005]; 
int trace[205][100005]; 

struct Convex_hull_linear {
	vector<pii> v; 
	int ptr = 0; 
	
	void init() {
		v.clear(); 
		ptr = 0; 
	}
	
	// y = kx + m; 
	double isect(ii x, ii y) {
		int k1 = x.fi, k2 = y.fi; 
		int m1 = x.se, m2 = y.se; 
		return (m2 - m1) * 1.0 / (k1 - k2) * 1.0; 
	}
	
	bool bad(ii a, ii b, ii c) {
		return isect(a, b) >= isect(b, c); 
	}
	
	void add(ii x, int id) {
		while(v.size() >= 2 and bad(v[v.size() - 2].fi, v[v.size() - 1].fi, x)) v.pop_back(); 
		v.pb({x, id}); 
	}
	
	int eval(ii Line, int x) {
		return Line.fi * x + Line.se; 
	}
	
	ii query(int x) {
		if(ptr > (int)v.size() - 1) {
			ptr = (int)v.size() - 1; 
		} // empty ? 
		while(ptr < (int)v.size() - 1 and eval(v[ptr].fi, x) <= eval(v[ptr + 1].fi, x)) { // omg this used to be < 
			ptr++; 
		}
		return {eval(v[ptr].fi, x), v[ptr].se};
	}
} Cvh;


signed main() {
//	freopen("test_input.txt", "r", stdin); 
	ios_base::sync_with_stdio(0); 
	cin.tie(0); 
	cout.tie(0); 
	cin >> n >> k; 
	for(int i = 1; i <= n; i++) {
		cin >> a[i]; 
		pre[i] = pre[i - 1] + a[i]; 
	}
	for(int j = 2; j <= k + 1; j++) {
		Cvh.init(); 
		Cvh.add({0, 0}, 0);
		for(int i = 1; i <= n; i++) {
			ii new_dp = Cvh.query(pre[i]); 
			Cvh.add({pre[i], dp[j - 1][i] - pre[i] * pre[i]}, i); 
			dp[j][i] = new_dp.fi;
			trace[j][i] = new_dp.se; 
		}
	}
	
	cout << dp[k + 1][n] << '\n'; 
	
	vector<int> res; 
	int trace_i = n; 
	for(int j = k + 1; j > 0; j--) {
		res.pb(trace[j][trace_i]); 
		trace_i = trace[j][trace_i]; 
	}
	
	reverse(res.begin(), res.end()); 
	for(auto x : res) {
		if(!x) continue; 
		cout << x << ' '; 
	}
}

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