Submission #135270

#	Time	Username	Problem	Language	Result	Execution time	Memory
135270		Lawliet	Split the sequence (APIO14_sequence)	C++14	71 / 100	2074 ms	85852 KiB

sequence

#include <bits/stdc++.h>
 
#define MAXK 210
#define MAXN 100010
#define INF 1000000000000000000LL
 
using namespace std;
typedef long long int lli;
 
int n, k;
 
int v[MAXN];
int opt[MAXN][MAXK];
 
lli sv[MAXN];
lli dp[MAXN][2];
 
lli cost(int l, int c, int r)
{
	lli firstPart = sv[c - 1] - sv[l - 1];
	lli secondPart = sv[r] - sv[c - 1];
 
	return firstPart*secondPart;
}
 
void DivAndConquer(int line, int l, int r, int optmin, int optmax)
{
	if(l > r) return;
 
	int m = (l + r)/2;
 
	int optInd = l;
	lli optValue = -1;
 
	for(int g = optmin ; g <= optmax && g <= m ; g++)
	{
		lli curAns = dp[g - 1][1 - line%2] + cost(1 , g , m);
 
		if(curAns > optValue)
		{
			optInd = g;
			optValue = curAns;
		}
	}
 
	dp[m][line%2] = optValue;
	opt[m][line] = optInd;
 
	DivAndConquer(line , l , m - 1 , optmin , optInd);
	DivAndConquer(line , m + 1 , r , optInd , optmax);
}
 
int main()
{
	scanf("%d %d",&n,&k);
 
	for(int g = 1 ; g <= n ; g++)
	{
		scanf("%d",&v[g]);
 
		sv[g] = sv[g - 1] + v[g];
	}
 
	dp[0][0] = dp[0][1] = -INF;
 
	for(int l = 1 ; l <= k ; l++)
		DivAndConquer(l , 1 , n , 2 , n);
 
	printf("%lld\n",dp[n][k%2]);
 
	int cur = n;
 
	for(int g = k ; g > 0 ; g--)
	{
		printf("%d ",opt[cur][g] - 1);
 
		cur = opt[cur][g] - 1;
	} 
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&k);
  ~~~~~^~~~~~~~~~~~~~~
sequence.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&v[g]);
   ~~~~~^~~~~~~~~~~~

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