Submission #1202216

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202216		crispxx	Split the sequence (APIO14_sequence)	C++20	0 / 100	0 ms	324 KiB

sequence

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

#define int long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define nl '\n'

template <typename A, typename B>
bool chmin(A &a, const B &b) {
	if(a > b) {
		return a = b, true;
	}
	return false;
}

template <typename A, typename B>
bool chmax(A &a, const B &b) {
	if(a < b) {
		return a = b, true;
	}
	return false;
}

void solve() {
	int n, k; cin >> n >> k;
	
	vector<int> a(n);
	
	for(auto &x : a) cin >> x;
	
	vector<int> pref(n + 1);
	
	for(int i = 0; i < n; i++) {
		pref[i + 1] = pref[i] + a[i];
	}
	
	auto sum = [&](int l, int r) {
		return pref[r + 1] - pref[l];
	};
	
	vector<int> choose(n - 1);
	
	for(int i = 0; i < k; i++) {
		choose[i] = 1;
	}
	
	reverse(all(choose));
	
	vector<int> v;
	
	int ans = 0;
	
	do {
		vector<int> p;
		for(int i = 0; i < n - 1; i++) {
			if(choose[i]) {
				p.pb(i);
			}
		}
		do {
			set<pair<int, int>> st;
			st.emplace(0, n - 1);
			int cur = 0;
			for(auto i : p) {
				auto [l, r] = *(--st.upper_bound({i, n}));
				cur += sum(l, i) * sum(i + 1, r);
				// cout << l << ' ' << r << nl;
				st.erase({l, r});
				st.emplace(l, i);
				st.emplace(i + 1, r);
			}
			// for(auto i : p) cout << i + 1 << ' ';
			// cout << ": " << cur << nl;
			if(ans < cur) {
				ans = cur;
				v = p;
			}
		} while(next_permutation(all(p)));
	} while(next_permutation(all(choose)));
	
	cout << ans << nl;
	for(auto i : v) {
		cout << i + 1 << ' ';
	}
	cout << nl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	solve();
}

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