Submission #977188

#	Time	Username	Problem	Language	Result	Execution time	Memory
977188		raspy	Split the sequence (APIO14_sequence)	C++14	0 / 100	32 ms	41004 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 m, int c, int m1, int c1)
{
	return (double)(c-c1)/(m1-m);
}

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].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-EPS)
			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();
		cht.push_back({{0, 0}, 0});
		for (int i = 1; i <= n; i++)
		{
			int p = gety(-vs[n]+vs[i]);
			ndp[i] = dp[p] + (vs[i]-vs[p])*(vs[n]-vs[i]);
			par[tk][i] = p;
			vstavi(vs[i], dp[i], i);
		}
		dp = ndp;
	}
	int tr = n, mx = dp[n];
	for (int i = 1; i <= n; i++)
	{
		if (dp[i] > mx)
		{
			mx = dp[i];
			tr = i;
		}
	}
	cout << mx << "\n";
	for (int i = k-1; i >= 0; 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