Submission #155040

#	Time	Username	Problem	Language	Result	Execution time	Memory
155040		aer0park	Split the sequence (APIO14_sequence)	C++14	0 / 100	111 ms	131076 KiB

sequence

#include <bits/stdc++.h>
#define f first
#define s second

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pi;

ll cnt,n,k,p[100006],a[100006],dp[100005][204];
int sv[100005][204];
vector<int> anw;

double get(ll a,ll b,ll q)
{
	return (double)(p[b]*p[b]-p[a]*p[a]+dp[a][q]-dp[b][q])/(double)(p[b]-p[a]);
}

ll push(ll x,ll c,ll d)
{
	while(cnt<c-1&&(x>=get(cnt,cnt+1,d)))	
		cnt++;
	sv[c][d+1]=cnt;
	return x*p[cnt]-p[cnt]*p[cnt]+dp[cnt][d];	
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		cin>>a[i],p[i]=p[i-1]+a[i];
	for(int i=1;i<=k;i++)
	{
		cnt=0;
		for(int j=1;j<=n;j++)
			dp[j][i]=push(p[j],j,i-1);	
	}
	cout<<dp[n][k]<<"\n";
	ll g=n;
	for(int i=k;i>=1;i--)
	{
		g=sv[g][i];
		anw.push_back(g);
	}
	reverse(anw.begin(),anw.end());
	for(int i=0;i<k;i++)
		cout<<anw[i]<<" ";
	return 0;
}

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