Submission #92527

#	Time	Username	Problem	Language	Result	Execution time	Memory
92527		davitmarg	Split the sequence (APIO14_sequence)	C++17	50 / 100	266 ms	11640 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[1003][1003];
int nxt[1003][1003];
LL sum(int l, int r)
{
	return pr[r] - pr[l - 1];
}

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

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

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 p = 1; p <= k; p++)
			dp[i][p] = -1;
	dfs(1,k);
	cout << dp[1][k] << endl;
	print(1,k);
	cout << endl;
	return 0;
}

/*

7 3
4 1 3 4 0 2 3 


*/

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