Submission #976875

#	Time	Username	Problem	Language	Result	Execution time	Memory
976875		raspy	Split the sequence (APIO14_sequence)	C++14	0 / 100	40 ms	10928 KiB

sequence

#include <iostream>
#include <vector>

#define inf 1'000'000'000
#define int long long
#define EPS 0.00001

using namespace std;

struct ln
{
	int m;
	int c;
	double p;
};

int a[100005];
int vs[100005];
int par[205][100005];
vector<int> dp(100005);
vector<int> ndp(100005);
vector<pair<ln, int>> cht;

double getx(int m, int c, int m1, int c1)
{
	return (double)(c-c1)/(m1-m);
}

pair<int, int> gety(int x)
{
	int rez = 0;
	int l = 0, d = cht.size()-1;
	while (l <= d)
	{
		int mid = (l+d)/2;
		if (cht[mid].first.p <= x+EPS)
			rez = mid, l = mid+1;
		else
			d = mid-1;
	}
	return {cht[rez].first.m*x+cht[rez].first.c, cht[rez].second};
}

void vstavi(int m, int c, int ix)
{
	double p = -inf;
	while (!cht.empty())
	{
		p = getx(m, c, cht.back().first.m, cht.back().first.c);
		if (p < cht.back().first.p)
			cht.pop_back();
		else
			break;
	}
	cht.push_back({{m, c, p}, ix});
}

int32_t main()
{
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		vs[i] = vs[i-1]+a[i];
	}
	for (int tk = 0; tk < k; tk++)
	{
		cht.clear();
		for (int i = 1; i <= n; i++)
		{
			if (i > 1)
			{
				auto p = gety(vs[i]);
				ndp[i] = p.first;
				par[tk][i] = p.second;
			}
			vstavi(vs[i], dp[i]-vs[i]*vs[i], i);
		}
		dp = ndp;
	}
	cout << dp[n] << "\n";
	int tr = n;
	for (int i = k-1; i >= 0; i--)
	{
		tr = par[i][tr];
		cout << tr << " ";
	}
	cout << "\n";
	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