Submission #216418

#	Time	Username	Problem	Language	Result	Execution time	Memory
216418		T0p_	Split the sequence (APIO14_sequence)	C++14	60 / 100	362 ms	131076 KiB

sequence

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

int n;
long long arr[100100];
pair<long long, int> dp[202][100100];
stack<int> pos;

void compute(int idx, int l, int r, int a, int b)
{
	int mid = (l+r)>>1;
	pair<long long, int> best = {-1, -1};
	for(int i=a ; i<=min(mid, b) ; i++)
	{
		long long nv = dp[idx-1][i].first + (arr[mid] - arr[i]) * (arr[n] - arr[mid]);
		if(nv > best.first) best = {nv, i};
	}
	dp[idx][mid] = best;
	if(l == r) return ;
	compute(idx, l, mid, a, best.second);
	compute(idx, mid+1, r, best.second, 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].first = arr[i] * (arr[n] - arr[i]);
	for(int i=2 ; i<=k ; i++)
		compute(i, 1, n, 1, n);
	pair<long long, int> best = {-1, -1};
	for(int i=1 ; i<=n ; i++)
		if(dp[k][i].first > best.first) best = {dp[k][i].first, i};
	printf("%lld\n",best.first);
	int p = best.second;
	for(int i=k ; i>=1 ; i--)
	{
		pos.push(p);
		p = dp[i][p].second;
	}
	while(!pos.empty())
	{
		printf("%d ",pos.top());
		pos.pop();
	}
	return 0;
}

Compilation message (stderr)

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

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