Submission #215919

#	Time	Username	Problem	Language	Result	Execution time	Memory
215919		T0p_	Split the sequence (APIO14_sequence)	C++14	0 / 100	49 ms	5368 KiB

sequence

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

int back[202][100100];
long long arr[100100], qs[100100], dp[202][100100];
stack<int> p;

int main()
{
	int n, m;
	scanf(" %d %d",&n,&m);
	for(int i=1 ; i<=n ; i++)
	{
		scanf(" %lld",&arr[i]); 
		qs[i] = arr[i] + qs[i-1];
	}
	for(int i=1 ; i<=m ; i++)
	{
		for(int j=i ; j<=n ; j++)
		{
			int l = i-1, r = j-1;
			while(l != r)
			{
				int mid = (l+r+1)>>1;
				int bef = mid-1;
				long long vm = dp[i-1][mid] + (qs[j] - qs[mid]) * (qs[n] - qs[j]);
				long long vb = dp[i-1][bef] + (qs[j] - qs[bef]) * (qs[n] - qs[j]);
				if(vm >= vb) l = mid;
				else r = mid-1;
			}
			dp[i][j] = dp[i-1][l] + (qs[j] - qs[l]) * (qs[n] - qs[j]);
			back[i][j] = l;
			// for(int k=i-1 ; k<j ; k++)
			// {
			// 	long long nv = dp[i-1][k] + (qs[j] - qs[k]) * (qs[n] - qs[j]);
			// 	if(nv > dp[i][j])
			// 	{
			// 		cout << i << ' ' << j << ' ' << k << endl;
			// 		dp[i][j] = nv;
			// 		pos = k;
			// 	}
			// }
			// back[i][j] = pos;
			// cout << back[i][j] << ' ';
		}
		// cout << endl;
	}
	int pos;
	long long Mval = 0;
	for(int i=m ; i<=n ; i++)
	{
		if(dp[m][i] > Mval)
		{
			Mval = dp[m][i];
			pos = i;
		}
	}
	for(int i=m ; i>0 ; i--)
	{
		p.push(pos);
		pos = back[i][pos];
	}
	printf("%lld\n",Mval);
	while(!p.empty())
	{
		printf("%d ",p.top());
		p.pop();
	}
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:11:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" %d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~~
sequence.cpp:14:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %lld",&arr[i]); 
   ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:61:20: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   pos = back[i][pos];
         ~~~~~~~~~~~^

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