제출 #135271

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
135271		Lawliet	Split the sequence (APIO14_sequence)	C++14	71 / 100	2056 ms	86732 KiB

sequence

#include <bits/stdc++.h>
 
#define MAXK 210
#define MAXN 100010
#define INF 1000000000000000000LL
 
using namespace std;
typedef long long int lli;
typedef pair<int,int> pii; 

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)
{
	queue<pii> q;

	q.push({1 , n});
	q.push({2 , n});

	while(!q.empty())
	{
		int L = q.front().first;
		int R = q.front().second;

		q.pop();

		int optmin = q.front().first;
		int optmax = q.front().second;

		q.pop();

		if(L > R) continue;

		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;

		q.push({L , m - 1});
		q.push({optmin , optInd});

		q.push({m + 1 , R});
		q.push({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 );
 
	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:77: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:81: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