Submission #104257

#	Time	Username	Problem	Language	Result	Execution time	Memory
104257		hugo_pm	Split the sequence (APIO14_sequence)	C++17	33 / 100	2044 ms	83832 KiB

sequence

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

#define int long long
#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= b; --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)

#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second

const long long BIG = 1000000000000000000LL;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

void cpr(string s, vector<int> v)
{ int i = 0; for (char c : s) { if (c == '$') cout << v[i++]; else cout << c; } cout << '\n'; }

void cpr(string s) { cpr(s, {}); }

void solve();
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	return 0;
}

const int maxElem = 100*1000 + 5;
const int maxParts = 205;

int nbElem, nbParts;
int val[maxElem];
int pr[maxElem];

int dp[maxElem][2];
signed tv[maxElem][maxParts];
int som = 0;

void proc(int splitRest, int elemLeft, int elemRight, int optLeft, int optRight)
{
	if (elemLeft > elemRight) return;
	int mode = splitRest % 2;
	int inv = 1-mode;

	int mid = (elemLeft + elemRight) / 2;
	int debOp = max(optLeft, mid+1);
	int finOp = max(optRight, debOp);

	int cs = 0;

	if (debOp >= 2) cs += pr[debOp-2];
	if (mid >= 1) cs -= pr[mid-1];

	int &ans = dp[mid][mode];
	ans = -BIG;

	int ww = -1;
	form2(opt, debOp, finOp+1) {
		cs += val[opt-1];
		int nw = cs * (som - cs) + dp[opt][inv];
		if (nw > ans) {
			ans = nw;
			ww = opt;
		} 
		if (nw < ans) break;
	}
	tv[mid][splitRest] = (signed)(ww);

	proc(splitRest, elemLeft, mid-1, optLeft, ww);
	proc(splitRest, mid+1, elemRight, ww, optRight);
}

void explorer(int curPos, int splitRestant)
{
	int nx = tv[curPos][splitRestant];
	if (nx == nbElem) return;
	cout << nx << " ";
	explorer(nx, splitRestant - 1);
}

void solve()
{
	cin >> nbElem >> nbParts;
	form(i, nbElem) {
		cin >> val[i];
		som += val[i];
		pr[i] = som;
	}
	form(i, nbElem) dp[i][0] = -BIG;
	dp[nbElem][0] = 0;
	form2(k, 1, nbParts+2) {
		dp[nbElem][k%2] = -BIG;
		proc(k, 0, nbElem-1, 0, nbElem);
	}
	cout << dp[0][(nbParts+1)%2]/2 << "\n";
	explorer(0, nbParts+1);
	cout << "\n";
}

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