Submission #414006

#	Time	Username	Problem	Language	Result	Execution time	Memory
414006		LastRonin	Split the sequence (APIO14_sequence)	C++14	100 / 100	1945 ms	82580 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 = 1E5 + 10;
 
ll n, k;
ll a[N];
ll dp[N][2];
int pr[N][203];
ll j = 1;
 
void dac(ll l, ll r, ll L, ll R) {
	if(l > r)return;
	ll m = (l + r) >> 1ll;
	for(int i = L; i <= min(R, m); i++) {
		if(dp[m][1] <= dp[i - 1][0] + (a[m] - a[i - 1]) * a[i - 1])
			dp[m][1] = dp[i - 1][0] + (a[m] - a[i - 1]) * a[i - 1],
			pr[m][j] = i;
	}
	dac(l, m - 1, L, pr[m][j]);
	dac(m + 1, r, pr[m][j], R);
}
 
int main() {
	speed;
	cin >> n >> k;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		a[i] += a[i - 1];
	}         
	for(int p = 1; p <= k; p++) {
		j = p;
		dac(1, n, 1, n);
		for(int i = 1; i <= n; i++)
			dp[i][0] = dp[i][1], dp[i][1] = 0;
	}
	/*for(int j = 1; j <= n; j++) {
	    for(int p = k; p >= 1; p--) {
			for(int i = j; i > p; i--) {
				if(dp[j][p] < dp[i - 1][p - 1] + (a[j] - a[i - 1]) * a[i - 1])
					dp[j][p] = max(dp[j][p], dp[i - 1][p - 1] + (a[j] - a[i - 1]) * a[i - 1]),
					pr[j][p] = i;
			}
		}
 	}*/
 	cout << dp[n][0] << '\n';
 	vector<ll> vost;
	ll x = n, y = k;
	while(y) {
		x = pr[x][y];
		y--;
		vost.pb(x);
		x--;
 	}
 	reverse(vost.begin(), vost.end());
 	for(auto u : vost)
 		cout << u - 1 << " ";
}
/*
7 3
4 1 3 4 0 2 3
*/

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