Submission #104247

#	Time	Username	Problem	Language	Result	Execution time	Memory
104247		hugo_pm	Split the sequence (APIO14_sequence)	C++17	0 / 100	119 ms	132096 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 dp[maxElem][maxParts];
int tv[maxElem][maxParts];
int som = 0;

int getDp(int curPos, int splitRestant)
{
	int &ans = dp[curPos][splitRestant];
	int &vers = tv[curPos][splitRestant];
	if (ans != -BIG-1) return ans;
	ans = -BIG;
	if (splitRestant == 0) {
		if (curPos == nbElem) ans = 0;
		else ans = -BIG;
		return ans;
	}
	if (curPos == nbElem) { ans = -BIG; return ans; }
	ans = -BIG;

	int cs = 0;
	form2(splitPos, curPos+1, nbElem+1) {
		cs += val[splitPos-1];
		int nw = cs * (som - cs) + getDp(splitPos, splitRestant-1);
		if (nw > ans) {
			ans = nw;
			vers = splitPos;
		}
	}
	return ans;
}

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

void solve()
{
	fill_n(&dp[0][0], maxElem * maxParts, -BIG-1);
	cin >> nbElem >> nbParts;
	form(i, nbElem) {
		cin >> val[i];
		som += val[i];
	}
	int fval = getDp(0, nbParts+1) / 2;
	cout << fval << "\n";
	explorer(0, nbParts+1);
}

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