Submission #548644

#	Time	Username	Problem	Language	Result	Execution time	Memory
548644		Zanite	Split the sequence (APIO14_sequence)	C++17	50 / 100	2076 ms	7528 KiB

sequence

// "I assure you that you guys won't make it to the top 4"
// - Tzaph, 21 December 2021

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define ll long long
#define ld long double
#define si short int
#define i8 __int128
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define psi pair<si, si>
#define pi8 pair<i8, i8>
#define pq priority_queue
#define fi first
#define se second

#define sqr(x) ((x)*(x))
#define pow2(x) (1ll << (x))
#define debug(x) cout << #x << " = " << (x) << '\n'
#define debugV(x, a) cout << #x << "[" << (a) << "] = " << (x[a]) << '\n'

#define yume using
#define wo namespace
#define kanaeyo std

yume wo kanaeyo;

template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
 
template<typename T> void maddto(T &a, T b, T mod) {a += b; a %= mod;}
template<typename T> void msubto(T &a, T b, T mod) {a -= b; while (a < 0) a += mod; a %= mod;}
template<typename T> void mmulto(T &a, T b, T mod) {a *= b; a %= mod;}
 
template<typename T> T madd(T a, T b, T mod) {a += b; a %= mod; return a;}
template<typename T> T msub(T a, T b, T mod) {a -= b; while (a < 0) a += mod; return a;}
template<typename T> T mmul(T a, T b, T mod) {a *= b; a %= mod; return a;}

const ll ModA = 998244353;
const ll ModC = 1e9 + 7;
const ll INF = 1e18;
const ll iINF = 1e9;

const ld EPS = 1e-9;
const ld iEPS = 1e-6;

const ll maxK = 202, maxN = 1e5 + 1;

ll n, k, a[maxN], pf[maxN];
ll dp[maxK][maxN], pred[maxK][maxN];

ll pref(ll l, ll r) {
	return pf[r] - pf[l-1];
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	cin >> n >> k;
	for (ll i = 1; i <= n; i++) {
		cin >> a[i];
		pf[i] = pf[i-1] + a[i];
	}

	for (ll i = 1; i <= n; i++) {
		dp[0][i] = -INF;
	}

	for (ll x = 1; x <= k+1; x++) {
		for (ll i = 1; i <= n; i++) {
			dp[x][i] = -INF;
			if (i >= x) {
				for (ll j = x-1; j < i; j++) {
					ll cur = dp[x-1][j] + 1ll * pref(1, j) * pref(j+1, i);
					if (cur > dp[x][i]) {
						dp[x][i] = cur;
						pred[x][i] = j;
					}
				}
			}
		}
	}

	cout << dp[k+1][n] << '\n';
	for (ll i = k+1, cur = n; i > 1; i--) {
		cout << pred[i][cur] << ' ';
		cur = pred[i][cur];
	}
	cout << '\n';
}

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