Submission #92512

#	Time	Username	Problem	Language	Result	Execution time	Memory
92512		davitmarg	Split the sequence (APIO14_sequence)	C++17	22 / 100	2075 ms	132080 KiB

sequence

/*
DEATH-MATCH
Davit-Marg
*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <iterator>
#include <ctype.h>
#include <stdlib.h>  
#include <cassert>
#include <fstream>  
#define mod 998244353ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
using namespace std;
int n,k,st;
LL a[100005],pr[100005],dp[202][202][202];
pair<int, int> nxt[202][202][202];
LL sum(int l, int r)
{
	return pr[r] - pr[l - 1];
}

void dfs(int l,int r,int k)
{
	if (k == 0)
		dp[l][r][k] = 0;
	if (dp[l][r][k] != -1)
		return;
	k--;
	for (int i = l; i < r; i++)
		for (int j = 0; j <= k && j < (i - l + 1) && k - j < r - i; j++)
		{
			dfs(l,i,j);
			dfs(i+1,r,k-j);
			LL d = sum(l, i)*sum(i + 1, r) + dp[l][i][j] + dp[i + 1][r][k - j];
			if (d > dp[l][r][k + 1])
			{
				dp[l][r][k + 1] = d;
				nxt[l][r][k + 1] = MP(i,j);
			}
		}
}

void print(int l,int r,int k)
{
	if (k <= 0)
		return;
	pair<int, int> p = nxt[l][r][k];
	cout << p.first << " ";
	k--;
	print(l,p.first,p.second);
	print(p.first + 1, r, k - p.second);
}

int main()
{
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		pr[i] = pr[i - 1] + a[i];
	}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			for (int p = 1; p <= k; p++)
				dp[i][j][p] = -1;
	dfs(1,n,k);
	cout << dp[1][n][k] << endl;
	print(1, n, k);
	cout << endl;
	return 0;
}

/*

7 3
4 1 3 4 0 2 3 


*/

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