Submission #530561

#	Time	Username	Problem	Language	Result	Execution time	Memory
530561		Hanksburger	Split the sequence (APIO14_sequence)	C++17	100 / 100	556 ms	83808 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
long long dp[100005][2], a[100005];
int back[100005][205], deq[100005];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, k, cur;
	cin >> n >> k;
	for (int i=1; i<=n; i++)
	{
		long long x;
		cin >> x;
		a[i]=a[i-1]+x;
	}
	for (int i=1; i<=k+1; i++)
	{
		deq[0]=i-1;
		int ii=i&1, iii=(i&1)^1, l=0, r=1;
		for (int j=i; j<=n; j++)
		{
//			cout << "i j " << i << ' ' << j << '\n';
			if (r-l>=2)
			{
				int x=deq[l], y=deq[l+1];
				while (dp[y][iii]-dp[x][iii]>=(a[n]-a[j])*(a[y]-a[x]))
				{
					l++;
//					cout << "deq pop back, now only have " << r-l << '\n';
					if (r-l<2)
						break;
					x=deq[l];
					y=deq[l+1];
				}
			}
			dp[j][ii]=dp[deq[l]][iii]+(a[n]-a[j])*(a[j]-a[deq[l]]);
			back[j][i]=deq[l];
			if (r-l>=2)
			{
				int x=deq[r-2], y=deq[r-1];
				while ((dp[y][iii]-dp[x][iii])*(a[j]-a[y])<=(dp[j][iii]-dp[y][iii])*(a[y]-a[x]))
				{
					r--;
//					cout << "deq pop back, now only have " << r-l << '\n';
					if (r-l<2)
						break;
					x=deq[r-2];
					y=deq[r-1];
				}
			}
			deq[r]=j;
			r++;
//			cout << "deq push back " << j << ", now have " << r-l << '\n';
		}
	}
	cout << dp[n][(k+1)&1] << '\n';
	cur=n;
	for (int i=k+1; i>=2; i--)
	{
		cur=back[cur][i];
		deq[i]=cur;
	}
	for (int i=2; i<=k+1; i++)
		cout << deq[i] << ' ';
	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