Submission #106058

#	Time	Username	Problem	Language	Result	Execution time	Memory
106058		Saboon	Split the sequence (APIO14_sequence)	C++14	100 / 100	1190 ms	83604 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;
const ll inf = 1e18;

ll a[maxn], par[maxn], dp[maxn];
int m[210][maxn];

struct line{
	ll a; // shib
	ll b; // arz az mabda
	int idx;
	line(ll a_ = 0, ll b_ = 0, int idx_ = 1){
		a = a_, b = b_, idx = idx_;
	}
	ll gety(ll x){
		return a * x + b;
	}
};

stack<line> Q;

bool isgood(line fi, line se, line th){
//	return 1ll * (se.b - fi.b) * (fi.a - th.a) < 1ll * (th.b - fi.b) * (fi.a - se.a);
	return 1. * (se.b - fi.b) / (fi.a - se.a) < 1. * (th.b - fi.b) / (fi.a - th.a);
}

bool parallel(line fi, line se){
	return fi.a == se.a;
}

void add(ll a, ll b, int idx){ // y = ax + b
	line nw = line(a, b, idx);
	if (!Q.empty() and parallel(nw, Q.top())){
		if (b > Q.top().b)
			Q.pop();
		else
			return;
	}
	while (Q.size() > 1){
		line nex = Q.top();
		Q.pop();
		line other = Q.top();
		if (isgood(other, nex, nw)){
			Q.push(nex);
			break;
		}
	}
	Q.push(nw);
}

pair<ll, int> get(ll x, int idx){
	while (!Q.empty() and Q.top().idx >= idx)
		Q.pop();
	if (Q.empty())
		return {-inf, 0};
	while (Q.size() > 1){
		line nw = Q.top();
		Q.pop();
		if (nw.gety(x) > Q.top().gety(x)){
			Q.push(nw);
			break;
		}
	}
//	cout << x << " -> " << Q.top().a << " " << Q.front().b << " " << Q.front().idx << endl;
	return {Q.top().gety(x), Q.top().idx};
}

void vitex(){
	while (!Q.empty())
		Q.pop();
}

int main(){
	ios_base::sync_with_stdio (false);
	int n, k;
	cin >> n >> k;
	k ++;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
		par[i] = par[i - 1] + a[i];
	}
	for (int i = 1; i <= k; i++){
		for (int j = n; j >= 1; j--){
			if (i == 1){
				dp[j] = 0;
				continue;
			}
			auto it = get(par[j], j);
			dp[j] = it.first;
			m[i][j] = it.second;
		}
		vitex();
		for (int j = 1; j <= n; j++)
			add(par[j], dp[j] - par[j] * par[j], j);
	}
	cout << dp[n] << endl;
	int p = k, q = n;
	while (p > 1){
		cout << m[p][q] << " ";
		q = m[p][q];
		p --;
	}
	cout << endl;
	return 0;
}

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