Submission #231348

#	Time	Username	Problem	Language	Result	Execution time	Memory
231348		peijar	Split the sequence (APIO14_sequence)	C++17	50 / 100	2090 ms	131076 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

#define SZ(v) ((int)(v).size())
using ll = long long;

const int MAXN = 1e5;
const int MAXK = 200;

ll dp[MAXN][MAXK];
ll arr[MAXN];
ll transition[MAXN][MAXK];
int nb_elem;

ll calc_dp(int cur, int nb_split)
{
	if (dp[cur][nb_split] != -1)
		return dp[cur][nb_split];
	if (nb_split == 0)
		return 0;
	if (cur==nb_elem)
		return -2e18;
	ll cumu_sum_lft(0), cumu_sum_rgt(0);
	for (int i(cur); i < nb_elem; ++i)
		cumu_sum_rgt += arr[i];
	for (int nxt(cur); nxt < nb_elem; ++nxt)
	{
		cumu_sum_lft += arr[nxt];
		cumu_sum_rgt -= arr[nxt];
		ll score = cumu_sum_rgt * cumu_sum_lft + calc_dp(nxt+1, nb_split-1);
		if (score > dp[cur][nb_split])
		{
			dp[cur][nb_split] = score;
			transition[cur][nb_split] = nxt;
		}
	}
	return dp[cur][nb_split];
}

int main(void)
{
	int nb_split;
	cin >> nb_elem >> nb_split;
	for (int i(0); i < nb_elem; ++i)
		cin >> arr[i];
	for (int i(0); i < nb_elem; ++i)
		for (int j(0); j <= nb_split; ++j)
			dp[i][j] = -1;
	cout << calc_dp(0, nb_split) << endl;
	int cur(0);
	for (int i(0); i < nb_split; ++i)
	{
		cur = transition[cur][nb_split-i] + 1;
		cout << cur << ' ';
	}
	cout << endl;

}

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