Submission #396603

#	Time	Username	Problem	Language	Result	Execution time	Memory
396603		wind_reaper	Split the sequence (APIO14_sequence)	C++17	60 / 100	2088 ms	88812 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

const int64_t INF = 1e18;

template<typename T>
struct LiChaoTree{
	static const T identity = 0;

	struct Line{
		T m, c;

		Line(){
			m = 0;
			c = identity;
		}

		Line(T m, T c) : m(m), c(c) {}

		T val(T x){
			return m*x + c;
		}
	};

	struct Node{
		Node *lc, *rc;
		Line line;
		int idx;

		Node() : lc(0), rc(0) {}
	};

	deque<Node> buffer;

	Node* new_node(){
		buffer.emplace_back();
		return &buffer.back();
	}

	Node *root;

	T L, R;
	void init(T L, T R){
		this->L = L;
		this->R = R;

		root = new_node();
	}

	void insert(Node* &node, T l, T r, Line line, int idx){
		if(!node){
			node = new_node();
			node->line = line;
			node->idx = idx;
			return;
		}

		if(r - l == 1)
			return;

		T mid = (l + r) >> 1;
		
		if(line.val(mid) > node->line.val(mid)){
			swap(line, node->line);
			swap(idx, node->idx);
		}

		if(line.val(l) > node->line.val(l)) insert(node->lc, l, mid, line, idx);
		else insert(node->rc, mid, r, line, idx);
	}

	pair<T, int> query(Node* &node, T l, T r, T x){
		if(!node)
			return {identity, 0};

		T mid = (l + r) >> 1;
		pair<T, int> res = {node->line.val(x), node->idx};

		if(r - l == 1)
			return res;

		if(x < mid) return max(res, query(node->lc, l, mid, x));
		else return max(res, query(node->rc, mid, r, x));
	}

	void clear(){
		buffer.clear();
	}

	void insert(T m, T c, int idx) { insert(root, L, R, Line(m, c), idx); }
	pair<T, int> query(T x) { return query(root, L, R, x); }
};

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N, K;
	cin >> N >> K;

	vector<int64_t> pref(N+1);
	for(int i = 1; i <= N; i++){
		cin >> pref[i];
		pref[i] += pref[i-1];
	}

	LiChaoTree<int64_t> dp[2];
	vector<vector<int>> par(K+1, vector<int>(N+1, -1));

	for(int i = 0; i < 2; i++)
		dp[i].init(0, 2e9);

	int64_t temp = 0;
	pair<int64_t, int> ans = {0, 0};

	for(int i = 1; i <= K; i++){
		int t = (i-1)&1, z = i&1;
		dp[z].clear();
		dp[z].init(0, 2e9);
		for(int j = 1; j < N; j++){
			pair<int64_t, int> q = dp[t].query(pref[N] - pref[j]); 
			temp = q.first + pref[j]*(pref[N] - pref[j]);
			int p = q.second;
			dp[z].insert(-pref[j], temp, j);
			ans = max(ans, {temp, j});
			par[i][j] = p;
		}
	}

	cout << ans.first << '\n';

	int nxt = ans.second;

	for(int i = K; i > 0; --i){
		cout << nxt << ' ';
		nxt = par[i][nxt];
	}

	return 0;
}

// dp[i][j] -> max val if the i th split is enacted on the j th place
// dp[i][j] = max over k(dp[i-1][k] + sum(k..j)*sum(j+1, n))
// dp = (pref[j])*(pref[n] - pref[j]) - pref[k]*(pref[n] - pref[j]) + dp[i-1][k];
// dp[1][1] -> (pref[n] - pref[1])*(pref[1] - pref[0]);

// dp[i][j] = max over z (dp[i-1][z] + (pref[j] - pref[z])*(pref[N] - pref[j]))
/*
4 1 3 4 0 2 3

6 3 1

4 1 3 4 0 2   3 -> 42
4 1 3  4 0 2  -> 48
4   1 3  -> 16
*/

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