Submission #215865

#	Time	Username	Problem	Language	Result	Execution time	Memory
215865		T0p_	Split the sequence (APIO14_sequence)	C++14	28 / 100	2099 ms	5424 KiB

sequence

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

int from[202][100100];
long long arr[100100], qs[100100], dp[202][100100];
stack<int> s;

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=1 ; j<=n ; j++)
		{
			int pos = 0;
			for(int k=0 ; k<j ; k++)
			{
				long long v = dp[i-1][k] + (qs[j] - qs[k])*(qs[n] - qs[j]);
				if(v > dp[i][j])
				{
					dp[i][j] = v;
					pos = k;
				}
			}
			from[i][j] = pos;
		}
	}
	int pos;
	long long Mval = 0;
	for(int i=1 ; i<=n ; i++)
	{
		if(dp[m][i] > Mval)
		{
			Mval = dp[m][i];
			pos = i;
		}
	}
	for(int i=m ; i>=1 ; i--)
	{
		s.push(pos);
		pos = from[i][pos];
	}
	printf("%lld\n",Mval);
	while(!s.empty())
	{
		printf("%d ",s.top());
		s.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:47:20: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   pos = from[i][pos];
         ~~~~~~~~~~~^

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