Submission #575258

#	Time	Username	Problem	Language	Result	Execution time	Memory
575258		denniskim	Split the sequence (APIO14_sequence)	C++17	0 / 100	234 ms	8624 KiB

sequence

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second

ll n, k;
ll a[100010];
ll nu[100010];
ll dp[100010];
ll last[100010];
ll l, r;
ll ans;
vector<ll> vec1, vec2;

struct CHT
{
	struct line_func
	{
		ll A, B;
		ld S;
		ll num;
	};
	
	line_func lin[100010];
	ll tp = 1;
	
	ld crossX(line_func X, line_func Y)
	{
		return (ld)(Y.B - X.B) / (ld)(X.A - Y.A);
	}
	
	void update(ll A, ll B, ll NUM)
	{
		line_func tmp;
		
		tmp.A = A;
		tmp.B = B;
		tmp.num = NUM;
		
		while(tp)
		{
			tmp.S = crossX(tmp, lin[tp]);
			
			if(tmp.S > lin[tp].S)
				break;
			
			tp--;
		}
		
		lin[++tp] = tmp;
	}
	
	pair<ll, ll> query(ll X)
	{
		ll LL = 1;
		ll RR = tp;
		
		while(LL <= RR)
		{
			ll mid = (LL + RR) / 2;
			
			if(lin[mid].S > X)
				RR = mid - 1;
			else
				LL = mid + 1;
		}
		
		return {lin[RR].A * X + lin[RR].B, lin[RR].num};
	}
}cht;

ll solve(ll lambda)
{
	for(ll i = 1 ; i <= n ; i++)
	{
		dp[i] = 0;
		last[i] = 0;
		cht.lin[i] = {0, 0, 0.0, 0};
	}
	
	cht.tp = 1;
	
	for(ll i = 1 ; i <= n ; i++)
	{
		pair<ll, ll> qry = cht.query(nu[i]);
		dp[i] = qry.fi + 2 * nu[i] * nu[i];
		last[i] = qry.se;
		cht.update(-4 * nu[i], dp[i] + 2 * nu[i] * nu[i] + lambda, i);
	}
	
	ll gaet = 0;
	
	for(ll i = n ; i != 0 ; i = last[i])
		gaet++;
	
	return gaet;
}

vector<ll> find_way(ll lambda)
{
	solve(lambda);
	
	vector<ll> vv;
	
	for(ll i = n ; i != 0 ; i = last[i])
		vv.push_back(i);
	
	vv.push_back(0);
	reverse(vv.begin(), vv.end());
	
	return vv;
}

int main(void)
{
	scanf("%lld %lld", &n, &k);
	
	k++;
	
	for(ll i = 1 ; i <= n ; i++)
	{
		scanf("%lld", &a[i]);
		nu[i] = nu[i - 1] + a[i];
	}
	
	l = 0;
	r = 1000000000000LL;
	
	while(l <= r)
	{
		ll mid = (l + r) / 2;
		ll lambda2 = mid * 2 + 1; //lambda * 2 = lambda2
		ll gap = solve(lambda2);
		
		if(gap >= k)
			l = mid + 1;
		else
			r = mid - 1;
	}
	
	ll gaet = solve(l * 2);
	ans = (dp[n] - (gaet - 1) * (l * 2)) / 2;
	
	printf("%lld\n", (nu[n] * nu[n] - ans) / 2);
	
	vec1 = find_way(r * 2 + 1);
	vec2 = find_way(l * 2 + 1);
	
	if((ll)vec1.size() == k + 1)
	{
		for(ll i = 1 ; i < (ll)vec1.size() - 1 ; i++)
			printf("%lld ", vec1[i]);
		
		return 0;
	}
	
	if((ll)vec2.size() == k + 1)
	{
		for(ll i = 1 ; i < (ll)vec2.size() - 1 ; i++)
			printf("%lld ", vec2[i]);
		
		return 0;
	}
	
	ll p = 0;
	
	for(ll i = 0 ; i < (ll)vec1.size() - 1 ; i++)
	{
		while(p < (ll)vec2.size() && vec2[p] <= vec1[i])
			p++;
		
		if(p == vec2.size())
			break;
		
		if(vec2[p - 1] <= vec1[i] && vec1[i + 1] <= vec2[p] && i + (ll)vec2.size() - p == k)
		{
			for(ll j = 1 ; j <= i ; j++)
				printf("%lld ", vec1[j]);
			
			for(ll j = p ; j < (ll)vec2.size() - 1 ; j++)
				printf("%lld ", vec2[j]);
			
			return 0;
		}
	}
	
	return -1;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:178:8: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |   if(p == vec2.size())
      |      ~~^~~~~~~~~~~~~~
sequence.cpp:122:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |  scanf("%lld %lld", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~
sequence.cpp:128:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |   scanf("%lld", &a[i]);
      |   ~~~~~^~~~~~~~~~~~~~~

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