Submission #241095

#	Time	Username	Problem	Language	Result	Execution time	Memory
241095		Berted	Split the sequence (APIO14_sequence)	C++14	100 / 100	1825 ms	82632 KiB

sequence

#include <iostream>
#include <assert.h>
#define ll long long
using namespace std;

const ll MN = -1e18;

int n, k, prt[202][100001] = {};
ll pref[100001][2] = {}, dp[2][100001] = {};

inline ll cost(int i, int j)
{
	ll t1 = pref[j][0] - pref[i - 1][0], t2 = pref[j][1] - pref[i - 1][1];
	return (t1 * t1 - t2) / 2;
}

void solve(int k, int L, int R, int lw, int up)
{
	int crk = k & 1, pk = !crk, M = L + R >> 1, opt = lw, nlw = min(M - 1, up);
	dp[crk][M] = MN;
	for (int i = lw; i <= nlw; i++)
	{
		if (dp[pk][i] - cost(i + 1, M) > dp[crk][M])
		{
			dp[crk][M] = dp[pk][i] - cost(i + 1, M);
			prt[k][M] = i;
			opt = i;
		}
	}
	if (L < R)
	{
		solve(k, L, M - 1, lw, opt);
		solve(k, M + 1, R, opt, up);
	}
}

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		cin >> pref[i][0];
		pref[i][1] = pref[i][0] * pref[i][0];
		pref[i][1] += pref[i - 1][1];
		pref[i][0] += pref[i - 1][0];
	}
	dp[0][0] = cost(1, n);
	for (int i = 1; i <= n; i++) dp[0][i] = MN;
	for (int i = 1; i <= k + 1; i++) solve(i, 0, n, 0, n);
	cout << dp[!(k & 1)][n] << "\n";
	for (int i = k + 1, cur = n; i > 1; i--)
	{
		cout << prt[i][cur];
		if (i > 2) cout << " ";
		cur = prt[i][cur];
	}
	cout << "\n";
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'void solve(int, int, int, int, int)':
sequence.cpp:19:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int crk = k & 1, pk = !crk, M = L + R >> 1, opt = lw, nlw = min(M - 1, up);
                                  ~~^~~

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