Submission #977896

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

sequence

#include <iostream>
#include <vector>

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

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 m1, int c1, int m2, int c2)
{
	return (double)(c1-c2)/(m2-m1);
}

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-EPS)
			cht.pop_back();
		else
			break;
	}
	cht.push_back({ {m, c, p}, ix });
}

pair<int, int> getBestY(int x)
{
	int k = 0;
	int L = 0, R = cht.size()- 1;
	while (L <= R)
	{
		int mid = (L+R) >> 1;
		if (cht[mid].first.p <= x+EPS)
			k = mid, L = mid+1;
		else
			R = mid-1;
	}
	return {cht[k].first.m*x+cht[k].first.c, cht[k].second};
}

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];
	}
	k++;
	for (int i = 1; i < k; i++)
	{
		cht.clear();
		vstavi(0, 0, 0);
		for (int j = 1; j <= n; j++)
		{
			pair<int, int> x = getBestY(vs[j]);
			ndp[j] = x.first + vs[j]*vs[n]-vs[j]*vs[j];
			par[i][j] = x.second;
			vstavi(vs[j], dp[j]-vs[j]*vs[n], j);
		}
		dp = ndp;
	}
	int tr = 1;
	for (int j = 1; j <= n; j++)
		if (dp[j] > dp[tr])
			tr = j;
	cout << dp[tr] << "\n";
	for (int i = k-1; i >= 1; i--)
	{
		cout << tr << " ";
		tr = par[i][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