Submission #554101

#	Time	Username	Problem	Language	Result	Execution time	Memory
554101		tutis	Split the sequence (APIO14_sequence)	C++17	0 / 100	2077 ms	11404 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 < 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];
	}
	pair<ll, int> dp1[n + 1][k + 1];
	for (int r = 1; r <= n; r++)
		dp1[r][1] = {0, -1};
	for (int k = 2; k <= n; k++)
	{
		reset();
		for (int r = k; r <= n; r++)
		{
			add(dp1[r - 1][k - 1].first - 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];
				dp1[r][k] = get(a[r]);
			}
		}
	}
	cout << dp1[n][k].first << "\n";
	vector<int>ans;
	while (k > 1)
	{
		n = dp1[n][k].second;
		ans.push_back(n);
		k--;
		assert(n >= 1 && k <= n);
	}
	sort(ans.begin(), ans.end());
	for (ll n : ans)
		cout << n << " ";
	cout << "\n";
}

Compilation message (stderr)

sequence.cpp: In function 'std::pair<long long int, int> get(ll)':
sequence.cpp:85:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |  while (itv + 1 < V.size())
      |         ~~~~~~~~^~~~~~~~~~

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