Submission #1089429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089429		Alihan_8	Split the sequence (APIO14_sequence)	C++17	100 / 100	765 ms	95060 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

#define pb push_back

using i64 = long long;

const i64 inf = 1e17;

int par[1000005][201];

struct Line{
	i64 m, c; int idx;
	
	Line(i64 m = 0, i64 c = -inf, int idx = -1) : m(m), c(c), idx(idx) {}
	
	i64 operator ()(i64 x){ return m * x + c; }
	
	bool isOpt(const Line &ff, const Line &ss){
		__int128 x = ff.c - c, y = ss.c - c;
		
		x *= m - ss.m, y *= m - ff.m;
		
		return x <= y;
	} 
};

signed main(){
	int n, k; cin >> n >> k; 
	
	k += 1;
	
	vector <i64> pf(n + 1);
	
	for ( int i = 0; i < n; i++ ){
		int x; cin >> x;
		
		pf[i + 1] = pf[i] + x;
	}
	
	vector <deque<Line>> dq(k + 1);
	
	for ( int i = 0; i <= k; i++ ) dq[i].pb(Line());
	
	auto add = [&](auto &dq, int j, i64 dp){
		Line cur = {pf[j], dp - pf[j] * pf[n], j};
		
		while ( (int)dq.size() > 1 && dq[(int)dq.size() - 2].isOpt(cur, dq.back()) ){
			dq.pop_back();
		} dq.pb(cur);
	};
	
	auto qry = [&](auto &dq, i64 x){
		while ( (int)dq.size() > 1 && dq[0](x) <= dq[1](x) ) dq.pop_front();
		
		return pair <i64,int> {dq[0](x), dq[0].idx};
	};
	
	vector <i64> dp(k + 1, -inf);
	
	dp[0] = 0; 
	
	add(dq[0], 0, 0); 
	
	for ( int i = 1; i <= n; i++ ){
		vector <i64> nxt(k + 1, -inf);
		
		for ( int j = 1; j <= k; j++ ){
			auto [v, p] = qry(dq[j - 1], pf[i]);
			
			v += (pf[n] - pf[i]) * pf[i];
			
			nxt[j] = v; par[i][j] = p;
		}
		
		for ( int j = 1; j <= k; j++ ){
			add(dq[j], i, nxt[j]);
		}
		
		swap(dp, nxt);
	}
	
	vector <int> p;
	
	int j = n;
	
	for ( int i = k; i > 1; i-- ){
		p.pb(par[j][i]);
		j = p.back();
	}
	
	cout << dp[k] << endl;
	
	for ( int i = k - 2; i >= 0; i-- ){
		cout << p[i] << ' ';
	}
	
	cout << '\n';
}

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