Submission #215936

#	Time	Username	Problem	Language	Result	Execution time	Memory
215936		T0p_	Split the sequence (APIO14_sequence)	C++14	50 / 100	2076 ms	5356 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);
	assert(m > 0);
	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++)
		{
			dp[i][j] = -1;
			int pos;
			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])
				{
					dp[i][j] = nv;
					pos = k;
				}
			}
			back[i][j] = pos;
		}
	}
	int pos;
	long long Mval = -1;
	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:15:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %lld",&arr[i]); 
   ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:49:20: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   pos = back[i][pos];
         ~~~~~~~~~~~^
sequence.cpp:33:15: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
    back[i][j] = pos;
    ~~~~~~~~~~~^~~~~

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