Submission #254553

#	Time	Username	Problem	Language	Result	Execution time	Memory
254553		babo	Split the sequence (APIO14_sequence)	C++14	0 / 100	12 ms	2688 KiB

sequence

#include <bits/stdc++.h>
#define L long long

using namespace std;

L n,k;
L a[1000010],nu[1000010];
L cut[1000010];

bool ok(L now){
	return cut[now]+1!=cut[now+1]&&
	(nu[cut[now]]-nu[cut[now-1]])*(nu[cut[now+1]]-nu[cut[now]])
	<(nu[cut[now]+1]-nu[cut[now-1]])*(nu[cut[now+1]]-nu[cut[now]+1]);
}

void dfs(L now){
	if(now==k) return;
	while(ok(now))
	{
		cut[now]++;
		dfs(now+1);
	}
	dfs(now+1);
	while(ok(now))
	{
		cut[now]++;
		dfs(now+1);
	}
}

int main()
{
	scanf("%lld %lld",&n,&k);
	k++;
	L i;
	for(i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		nu[i]=a[i]+nu[i-1];
		cut[i]=i;
	}
	cut[k]=n;
	dfs(1);
	L ans=nu[n]*nu[n];
	for(i=1;i<=k;i++)
		ans-=(nu[cut[i]]-nu[cut[i-1]])*(nu[cut[i]]-nu[cut[i-1]]);
	ans/=2;
	printf("%lld\n",ans);
	for(i=1;i<k;i++)
		printf("%lld ",cut[i]);
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld",&n,&k);
  ~~~~~^~~~~~~~~~~~~~~~~~~
sequence.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   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