Submission #215945

#	Time	Username	Problem	Language	Result	Execution time	Memory
215945		T0p_	Split the sequence (APIO14_sequence)	C++14	11 / 100	42 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 pos;
			int l = i-1, r = j-1;
			while(l != r)
			{
				int mid = (l+r+1)>>1;
				long long vm = dp[i-1][mid] + (qs[j] - qs[mid]) * (qs[n] - qs[j]);
				long long vb = dp[i-1][mid-1] + (qs[j] - qs[mid-1]) * (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;
		}
	}
	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:21:8: warning: unused variable 'pos' [-Wunused-variable]
    int pos;
        ^~~
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:48:20: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   pos = back[i][pos];
         ~~~~~~~~~~~^

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