제출 #530558

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
530558		Hanksburger	Split the sequence (APIO14_sequence)	C++17	71 / 100	52 ms	131076 KiB

sequence

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