Submission #538683

#	Time	Username	Problem	Language	Result	Execution time	Memory
538683		S2speed	Split the sequence (APIO14_sequence)	C++17	100 / 100	1298 ms	82300 KiB

sequence

#include<bits/stdc++.h>

using namespace std;

#define all(x) x.begin() , x.end()
typedef long long ll;

const ll maxn = 1e5 + 16 , inf = 2e18;

ll a[maxn] , ps[maxn] , dp[maxn] , pd[maxn];
int opt[216][maxn];

ll cost(ll l , ll r){
	ll res = ps[r] - (l ? ps[l - 1] : 0);
	res *= res;
	return res;
}

void dv(ll l , ll r , ll opl , ll opr , ll j){
	if(l >= r) return;
	ll m = (r + l) >> 1 , lm = min(m - 1 , opr);
	dp[m] = inf;
	ll ind = -1;
	for(ll i = opl ; i <= lm ; i++){
		ll h = pd[i] + cost(i + 1 , m);
		if(h < dp[m]){
			dp[m] = h;
			ind = i;
		}
	}
	opt[j][m] = ind;
	dv(l , m , opl , ind , j); dv(m + 1 , r , ind , opr , j);
	return;
}

vector<ll> v;

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

	ll n , k;
	cin>>n>>k;
	for(ll i = 0 ; i < n ; i++){
		cin>>a[i];
	}
	ps[0] = a[0];
	for(ll i = 1 ; i < n ; i++){
		ps[i] = ps[i - 1] + a[i];
	}
	for(ll i = 0 ; i < n ; i++){
		pd[i] = ps[i] * ps[i];
	}
	for(ll j = 1 ; j <= k ; j++){
		dv(j , n , j - 1 , n - 1 , j);
		memcpy(pd , dp , sizeof(dp));
	}
//	for(ll i = 0 ; i < n ; i++){
//		cout<<pd[i]<<' ';
//	}
//	cout<<'\n';
	ll h = ps[n - 1] * ps[n - 1] - dp[n - 1]; h >>= 1ll;
	cout<<h<<'\n';
	ll p = n - 1 , j = k;
	while(~j){
		v.push_back(p);
		p = opt[j--][p];
	}
	reverse(all(v));
	for(ll i = 0 ; i < k ; i++){
		cout<<v[i] + 1<<' ';
	}
	cout<<'\n';
	return 0;
}

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