Submission #308033

#	Time	Username	Problem	Language	Result	Execution time	Memory
308033		avengers	Split the sequence (APIO14_sequence)	C++14	0 / 100	14 ms	7808 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
using ll=long long int;
typedef struct Line{
	ll p, q;
}line;
int n, k;
ll a[100005];
ll s[100005]={};
int track[205][100005];
line cht[100005];
ll sz=0;
ll now=0;
double cx(line a, line b)
{
	return 1.0*(double)(b.q-a.q)/(a.p-b.p);
}
void insert(line v)
{
	cht[sz]=v;
	while(sz>1&&cx(cht[sz-2], cht[sz-1])>cx(cht[sz], cht[sz-1]))
	{
		cht[sz-1]=cht[sz];
		sz--;
	}
	sz++;
}
pair <ll, ll> sol(ll x)
{
	while(now<sz-1&&cx(cht[now], cht[now+1])<=x) now++;
	return {cht[now].p*x+cht[now].q, now};
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	ll dp[k+1][n+1];
	for(int i=0; i<=k; i++)
	{
		for(int j=0; j<=n; j++) dp[i][j]=0;
	}
	for(int i=1; i<=n; i++)
	{
		cin>>a[i];
		s[i]=s[i-1]+a[i];
	}
	line l;
	for(int i=1; i<=k; i++)
	{
		l.p=0;
		l.q=0;
		insert(l);
		for(int j=1; j<=n; j++)
		{
			pair <ll, ll> p=sol(s[j]);
			dp[i][j]=p.first;
			track[i][j]=p.second;
			l.p=s[j];
			l.q=dp[i-1][j]-s[j]*s[j];
			insert(l);
		}
		sz=0;
		now=0;
	}
	cout<<dp[k][n]<<'\n';
	vector <int> ans;
	ll cur=n;
	for(int i=k; i>=1; i--)
	{
		ans.push_back(track[i][cur]);
		cur=track[i][cur];
	}
	reverse(ans.begin(), ans.end());
	for(auto i:ans) cout<<i<<' ';
}

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