Submission #1288530

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288530		harryleee	Split the sequence (APIO14_sequence)	C++20	0 / 100	1 ms	344 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5;
int n, k, a[maxn + 1], pre[maxn + 1], trace[maxn + 1][201];
long long dp[maxn + 1][201], st;

struct line{
	long long a, b;
	mutable long double p;
	int id;
	bool operator < (const line other)const{
		if (other.a == 1e18 && other.b == 1e18) return p < other.p;
		return a < other.a;
	}
};
struct LINE_CONTAINER{
	multiset<line> ms;
	inline bool del(multiset<line>::iterator x, multiset<line>::iterator y){
		if (y == ms.end()){
			x->p = 1e18;
			return false;
		}
		if (x->a == y->a){
			x->p = (x->b >= y->b) ? 1e18 : -1e18;
		}
		else x->p = (long double)(y->b - x->b) / (long double)(x->a - y->a);
		return x->p >= y->p;
	}
	inline void update(long long a, long long b, int i){
		multiset<line>::iterator x = ms.insert({a, b, 0, i}), y = next(x);
		while(del(x, y)) y = ms.erase(y);
		if (x != ms.begin()){
			y = prev(x);
			if (del(y, x)) ms.erase(x);
		}
		else y = x;
		while(y != ms.begin()){
			x = prev(y);
			if (del(x, y)){
				del(x, ms.erase(y));
				y = x;
			}
			else break;
		}
	}
	inline pair<long long, int> get(long long x){
		multiset<line>::iterator it = ms.lower_bound({(long long)1e18, (long long)1e18, (long double)x});
		if (it == ms.end()) return {-1e18, 0};
		return {it->a * x + it->b, it->id};
	}
};

int main(){
	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];
	}

	LINE_CONTAINER lc[k];
	lc[0].update(0, 0, 0);
	dp[0][k] = -1e18;
	for (int i = 1; i <= n; ++i){
		for (int j = 1; j <= min(i, k); ++j){
			pair<long long, int> g = lc[j - 1].get(pre[n] - pre[i]);
			dp[i][j] = g.first + pre[i] * (pre[n] - pre[i]);
			if (j < k) lc[j].update(-pre[i], dp[i][j], i);
			if (i < n && j == k && dp[i][k] > dp[st][k]) st = i;
			trace[i][j] = g.second;
		}
	}
	cout << dp[st][k] << '\n';
	vector<int> v;
	while(st != 0){
		v.push_back(st);
		st = trace[st][k--];
	}
	reverse(v.begin(), v.end());
	for (int i : v) cout << i << ' ';
	return 0;
}

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