Submission #344482

#	Time	Username	Problem	Language	Result	Execution time	Memory
344482		wwdd	Split the sequence (APIO14_sequence)	C++14	100 / 100	1312 ms	82680 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
const int MN = 100100;
const int MK = 222;
const ll INFL = 1e18;
vl w,pr;
ll dp[2][MN];
int pd[MK][MN];
void ds(ll ro, ll l, ll r, ll kl, ll kr) {
	if(l > r) {return;}
	ll m = (l+r)/2;
	ll mo = kl;
	ll mv = -1;
	for(int i=kl;i<=min(m-1,kr);i++) {
		ll pk = dp[(ro&1)^1][i] + pr[i]*(pr[m]-pr[i]);
		if(pk > mv) {mv = pk;mo = i;}
	}
	dp[ro&1][m] = mv;
	pd[ro][m] = mo;
	ds(ro,l,m-1,kl,mo);
	ds(ro,m+1,r,mo,kr);
}
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	memset(dp,0,sizeof(dp));
	int n,k;
	cin >> n >> k;
	pr.push_back(0);
	for(int i=0;i<n;i++) {
		ll t;
		cin >> t;
		w.push_back(t);
		pr.push_back(pr.back()+t);
	}
	for(int i=1;i<=k;i++) {
		ds(i,i+1,n,i,n);
	}
	vl res;
	ll bak = n;
	for(int i=k;i>0;i--) {
		res.push_back(pd[i][bak]);
		bak = res.back();
	}
	cout << dp[k&1][n] << '\n';
	reverse(res.begin(),res.end());
	for(int i=0;i<k;i++) {
		if(i > 0) {cout << " ";}
		cout << res[i];
	}
	cout << '\n';
}

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