Submission #26027

#	Time	Username	Problem	Language	Result	Execution time	Memory
26027		nibnalin	Split the sequence (APIO14_sequence)	C++14	50 / 100	356 ms	5252 KiB

sequence

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

typedef long long int lli;

const lli maxn = 1005, maxk = 205, inf = lli(1e9)+5;

lli A[maxn], p[maxn];
pair<lli, lli> dp[maxn][maxk];

int main(void)
{
	lli n, k;
	scanf("%lld%lld", &n, &k);
	for(lli i = 1;i <= n;i++) scanf("%lld", &A[i]);
	for(lli i = 1;i <= n;i++) p[i] = A[i]+p[i-1];


	for(lli kk = 1;kk <= k;kk++)
	{
		for(lli i = 1;i <= n;i++)
		{
			dp[i][kk] = {-inf, -1};
			for(lli j = 0;j < i;j++)
			{
				dp[i][kk] = max(dp[i][kk], {dp[j][kk-1].first+(p[i]-p[j])*p[j], j});
			}
		}
	}

	printf("%lld\n", dp[n][k].first);

	lli idx = n;
	for(lli kk = k;kk > 0;kk--)
	{
		printf("%lld ", dp[idx][kk].second);
		idx = dp[idx][kk].second;
	}
	printf("\n");
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:16:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld", &n, &k);
                           ^
sequence.cpp:17:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(lli i = 1;i <= n;i++) scanf("%lld", &A[i]);
                                                ^

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