Submission #216437

#	Time	Username	Problem	Language	Result	Execution time	Memory
216437		T0p_	Split the sequence (APIO14_sequence)	C++14	100 / 100	1604 ms	81048 KiB

sequence

#include<bits/stdc++.h>
using namespace std;

int n;
int pos[202][100100];
long long arr[100100];
long long dp[2][100100];
stack<int> ans;

void compute(int idx, int l, int r, int a, int b)
{
	int mid = (l+r)>>1;
	for(int i=a ; i<=min(mid, b) ; i++)
	{
		long long nv = dp[(idx-1)%2][i] + (arr[mid] - arr[i]) * (arr[n] - arr[mid]);
		if(nv > dp[idx%2][mid])
		{
			dp[idx%2][mid] = nv;
			pos[idx][mid] = i;
		}
	}
	if(l == r) return ;
	compute(idx, l, mid, a, pos[idx][mid]);
	compute(idx, mid+1, r, pos[idx][mid], b);
}

int main()
{
	int k;
	scanf(" %d %d",&n,&k);
	for(int i=1 ; i<=n ; i++)
	{
		scanf(" %lld",&arr[i]);
		arr[i] += arr[i-1];
	}
	for(int i=1 ; i<=n ; i++)
		dp[1][i] = arr[i] * (arr[n] - arr[i]);
	for(int i=2 ; i<=k ; i++)
	{
		for(int j=1 ; j<=n ; j++)
			dp[i%2][j] = 0;
		compute(i, i, n, 1, n);
	}
	long long mv = -1;
	int p;
	for(int i=k ; i<n ; i++)
		if(dp[k%2][i] > mv)
		{
			mv = dp[k%2][i];
			p = i;
		}
	printf("%lld\n",mv);
	for(int i=k ; i>=1 ; i--)
	{
		ans.push(p);
		p = pos[i][p];
	}
	while(!ans.empty())
	{
		printf("%d ",ans.top());
		ans.pop();
	}
	return 0;
}
/*
7 3
4 1 3 4 0 2 3
*/

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:30: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:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %lld",&arr[i]);
   ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:56:15: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   p = pos[i][p];
       ~~~~~~~~^

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