Submission #530555

#	Time	Username	Problem	Language	Result	Execution time	Memory
530555		Hanksburger	Split the sequence (APIO14_sequence)	C++17	0 / 100	59 ms	131076 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
long long back[100005][205], dp[100005][2], a[100005], b[100005];
vector<long long> vec, 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++)
	{
		vec.clear();
		vec.push_back(i-1);
		long long ii=i&1, iii=(i&1)^1, sz=1;
		for (long long j=i; j<=n; j++)
		{
//			cout << "i j " << i << ' ' << j << '\n';
			if (sz>=2)
			{
				long long x=vec[sz-2], y=vec[sz-1];
				while (dp[y][iii]-dp[x][iii]<=(b[n]-b[j])*(b[y]-b[x]))
				{
					vec.pop_back();
					sz--;
//					cout << "vec pop back, now only have " << sz << '\n';
					if (sz<2)
						break;
					x=vec[sz-2];
					y=vec[sz-1];
				}
			}
			dp[j][ii]=dp[vec[sz-1]][iii]+(b[n]-b[j])*(b[j]-b[vec[sz-1]]);
			back[j][i]=vec[sz-1];
			if (sz>=2)
			{
				long long x=vec[sz-2], y=vec[sz-1];
				while ((dp[y][iii]-dp[x][iii])*(b[j]-b[y])<(dp[j][iii]-dp[y][iii])*(b[y]-b[x]))
				{
					vec.pop_back();
					sz--;
//					cout << "vec pop back, now only have " << sz << '\n';
					if (sz<2)
						break;
					x=vec[sz-2];
					y=vec[sz-1];
				}
			}
			sz++;
			vec.push_back(j);
//			cout << "vec push back " << j << ", now have " << sz << '\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: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29