제출 #135217

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
135217		Lawliet	수열 (APIO14_sequence)	C++14	49 / 100	2064 ms	85988 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] = 0;

	for(int g = 1 ; g <= n ; g++)
		dp[g][0] = 0;

	for(int l = 1 ; l <= k ; l++)
		DivAndConquer(l , 1 , n , 1 , 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;
	} 
}

컴파일 시 표준 에러 (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: 0 / 11
• Subtask 2: 11 / 11
• Subtask 3: 0 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 0 / 29