Submission #977213

#	Time	Username	Problem	Language	Result	Execution time	Memory
977213		raspy	Split the sequence (APIO14_sequence)	C++14	0 / 100	46 ms	11480 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 });
}

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