Submission #554109

#	Time	Username	Problem	Language	Result	Execution time	Memory
554109		tutis	Split the sequence (APIO14_sequence)	C++17	100 / 100	755 ms	84748 KiB

sequence

/*input
7 3
4 1 3 4 0 2 3
*/
#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
using namespace std;
//using ull = __ull128_t;
using ull = unsigned long long;
using ll = long long;
using ld = long double;
ll mod = 1e9 + 7;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll power(ll a, ll b)
{
	if (abs(a) >= mod)
		a %= mod;
	if (abs(b) >= mod - 1)
		b %= (mod - 1);
	if (a < 0)
		a += mod;
	if (b < 0)
		b += mod - 1;
	ll r = 1;
	if (b % 2 == 1)
		r = a;
	b /= 2;
	while (b)
	{
		a = (a * a) % mod;
		if (b % 2 == 1)
			r = (r * a) % mod;
		b /= 2;
	}
	return r;
}
vector<pair<ll, ll>>V;
vector<int>Vi;
int itv = 0;
void reset()
{
	V.clear();
	Vi.clear();
	itv = 0;
}
ld C(pair<ll, ll>a, pair<ll, ll>b)
{
	ld k = a.first - b.first;
	ld c = a.second - b.second;
	//kx+c=0;
	return -c / k;
}
void add(ll c, ll k, int i)
{
	if (V.size() > 0 && V.back().first == k && V.back().second >= c)
		return;
	if (V.size() > 0 && V.back().first == k)
	{
		V.back().second = c;
		Vi.back() = i;
	}
	else {
		V.push_back({k, c});
		Vi.push_back(i);
	}
	while (V.size() >= 3)
	{
		pair<ll, ll>a = V[V.size() - 3];
		pair<ll, ll>b = V[V.size() - 2];
		pair<ll, ll>c = V[V.size() - 1];
		if (C(a, b) > C(b, c) + 1e-9)
		{
			V.erase(V.begin() + (V.size() - 2));
			Vi.erase(Vi.begin() + (Vi.size() - 2));
		}
		else
			break;
	}
}
pair<ll, int> get(ll x)
{
	itv = min(itv, (int)V.size() - 1);
	ll v = V[itv].first * x + V[itv].second;
	while (itv + 1 < (int)V.size())
	{
		ll v1 = V[itv + 1].first * x + V[itv + 1].second;
		if (v1 >= v)
		{
			v = v1;
			itv++;
		}
		else
			break;
	}
	while (itv > 0)
	{
		ll v1 = V[itv - 1].first * x + V[itv - 1].second;
		if (v1 >= v)
		{
			v = v1;
			itv--;
		}
		else
			break;
	}
	return {v, Vi[itv]};
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int n, K;
	cin >> n >> K;
	K++;
	ll a[n + 1];
	a[0] = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		a[i] += a[i - 1];
	}
	ll dp[n + 1][2];
	int dp1[n + 1][K + 1];
	for (int r = 1; r <= n; r++)
		dp[r][1] = 0;
	for (int k = 2; k <= K; k++)
	{
		int k1 = (k - 1) % 2;
		int k2 = k % 2;
		reset();
		for (int r = k; r <= n; r++)
		{
			add(dp[r - 1][k1] - a[r - 1] * a[r - 1], a[r - 1], r - 1);
			//for (int r1 = k - 1; r1 <= r - 1; r1++)
			{
				//ll gal = dp1[r1][k - 1].first - a[r1] * a[r1] + a[r] * a[r1];
				pair<ll, int>v = get(a[r]);
				dp[r][k2] = v.first;
				dp1[r][k] = v.second;
			}
		}
	}
	int k = K;
	cout << dp[n][k % 2] << "\n";
	vector<int>ans;
	while (k > 1)
	{
		n = dp1[n][k];
		ans.push_back(n);
		k--;
		assert(n >= 1 && k <= n);
	}
	sort(ans.begin(), ans.end());
	for (ll n : ans)
		cout << n << " ";
	cout << "\n";
}

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