Submission #412590

#	Time	Username	Problem	Language	Result	Execution time	Memory
412590		LastRonin	Split the sequence (APIO14_sequence)	C++14	11 / 100	2072 ms	72144 KiB

sequence

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
using namespace std;

const ll N = 2e2 + 10;

ll n, k;
ll dp[N][N][N];
pair<int, int> p[N][N][N];
bool was[N][N][N];
ll a[N];  

ll sum(ll l, ll r) {
	return a[r] - a[l - 1];
}

ll calc(ll l, ll r, ll k) {
	if(k == 0)
		return 0;
	if(was[l][r][k])
		return dp[l][r][k];
	was[l][r][k] = 1;
	for(int i = l; i < r; i++) {
		for(int j = 0; j < k; j++) {
			if(i - l < j || r - i - 1 < k - j - 1)
				continue;
			ll z = sum(l, i) * sum(i + 1, r) + calc(l, i, j) + calc(i + 1, r, k - j - 1);
			if(dp[l][r][k] < z)
				dp[l][r][k] = z, p[l][r][k] = mp(i, j);			
		}
	}
	return dp[l][r][k];
}

int main() {
	speed;
	cin >> n >> k;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		a[i] += a[i - 1];
	}
	cout << calc(1, n, k) << '\n';
	vector<pair<int, pair<int ,int>>> q;
	vector<int> raz;
	q.pb(mp(k, mp(1, n)));
	while((ll)q.size()) {
		ll L = q.back().s.f, R = q.back().s.s, rp = q.back().f;
		q.pop_back();        	
		if(rp == 0) 
        	continue;        
        raz.pb(p[L][R][rp].f);
		q.pb(mp(p[L][R][rp].s, mp(L, p[L][R][rp].f)));
    	q.pb(mp(rp - p[L][R][rp].s - 1, mp(p[L][R][rp].f + 1, R)));

	}
	sort(raz.begin(), raz.end());
	for(auto u : raz)
		cout << u << " ";
}
/*
7 3
4 1 3 4 0 2 3
*/

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