Submission #45576

#	Time	Username	Problem	Language	Result	Execution time	Memory
45576		Pajaraja	Split the sequence (APIO14_sequence)	C++17	0 / 100	29 ms	4900 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
long long dp[100007],dpl[100007],s[100007],a[100007];
int pre[207][100007];
int main()
{
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++) scanf("%lld",&a[i]);
	s[0]=a[0];
	for(int i=1;i<n;i++) s[i]=s[i-1]+a[i];
	for(int i=0;i<n;i++) dpl[i]=2*s[i]*s[i];
	for(int t=2;t<=k+1;t++)
	{
		int p=t-2;
		for(int i=t-1;i<n;i++)
		{
			while(dpl[p]-2*s[i]*s[p]>dpl[p+1]-2*s[i]*s[p+1] && p<i-1) p++;
			dp[i]=dpl[p]-2*s[i]*s[p]+2*s[i]*s[i];
			pre[t][i]=p;
		}
		for(int i=0;i<n;i++) {dpl[i]=dp[i];}
	}
	long long sol=(2*s[n-1]*s[n-1]-dpl[n-1])/2;
	printf("%lld\n",sol);
	int cur=pre[k+1][n-1];
	for(int i=k;i>0;i--)
	{
		printf("%d ",cur+1);
		cur=pre[i][cur];
	}
}

Compilation message (stderr)

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