Submission #41684

#	Time	Username	Problem	Language	Result	Execution time	Memory
41684		Diuven	Split the sequence (APIO14_sequence)	C++11	71 / 100	2040 ms	81260 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX=100010;
const ll inf=4e18;
int S[MX], n, k, P[MX][201];
ll D[MX][2];
ll sq(ll x){ return x*x; }
void solve(int s, int e, int l, int r, int t){
	if(e<s) return;
	int m=(s+e)/2, &pos=P[m][t]; ll &d=D[m][t&1]; d=inf, pos=s;
	for(int i=l; i<=r && i<m; i++){
		ll now=D[i][1-(t&1)]+sq(S[m]-S[i]);
		if(d>now) d=now, pos=i;
	}
	solve(s,m-1,l,pos,t);
	solve(m+1,e,pos,r,t);
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>n>>k;
	for(int i=1, a; i<=n; i++)
		cin>>a, S[i]=S[i-1]+a, D[i][0]=sq(S[i]);
	for(int i=1; i<=k; i++)
		solve(1,n,1,n,i);
	cout<<(sq(S[n])-D[n][k&1])/2<<'\n';
	stack<int> stk;
	for(int i=k, pos=n; i>=1; i--){
		pos=P[pos][i];
		stk.push(pos);
	}
	while(!stk.empty()) cout<<stk.top()<<' ', stk.pop();
	return 0;
}

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