Submission #854509

#	Time	Username	Problem	Language	Result	Execution time	Memory
854509		parsadox2	Split the sequence (APIO14_sequence)	C++14	100 / 100	1547 ms	83244 KiB

sequence

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 1e5 + 2 , K = 2e2 + 2;
int n , k , from[N][K] , a[N] , p[N];
long long dp[N][2] , A[N];
 
inline long long Add(int i , int id)
{
	return A[id] + 1LL * p[i] * p[id];
}
 
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);  cout.tie(0);
	cin >> n >> k;
	for(int i = 1 ; i <= n ; i++)
		cin >> a[i];
	k++;
	for(int i = 1 ; i <= n ; i++)
		p[i] = p[i - 1] + a[i];
	for(int j = 2 ; j <= k ; j++)
	{
		int now = (j & 1) , prv = now ^ 1;
		deque <pair<int , int>> dq;
		dp[j - 1][now] = 0;
		A[j - 1] = -1LL * p[j - 1] * p[j - 1] + dp[j - 1][prv];
		dq.push_back({j , j - 1});
		for(int i = j ; i <= n ; i++)
		{
			auto noww = dq.front();
			int id = noww.second;
			dp[i][now] = Add(i , id);
			//cout << i << " : " << j << " : " << dp[i][now] << endl;
			from[i][j] = id;
			A[i] = dp[i][prv] - 1LL * p[i] * p[i];
			if(i == n)
				break;
			dq.pop_front();
			if(dq.empty() || dq.front().first > noww.first + 1)
				dq.push_front(make_pair(noww.first + 1 , noww.second));
			int las = n + 1;
			while(!dq.empty())
			{
				//cout << "RANGOOL" << endl;
				noww = dq.back();
				if(Add(noww.first , i) >= Add(noww.first , noww.second))
				{
					dq.pop_back();
					las = noww.first;
					continue;
				}
				id = noww.second;
				//cout << p[i] - p[id] << endl;
				long long tmp = 1LL * (A[id] - A[i] + p[i] - p[id]) / (p[i] - p[id]);
				//cout << "SALAM" << endl;
				int low = noww.first , high = las;
				while(high - low > 1)
				{
					int mid = (low + high) >> 1;
					if(p[mid] >= tmp)
						high = mid;
					else
						low = mid;						
				}
				las = high;
				break;
			}
			//cout << i << " " << las << endl;
			if(las != n + 1)
				dq.push_back({las , i});
		}
	}
	cout << dp[n][(k & 1)] << endl;
	vector <int> all;
	while(k > 1)
	{
		all.push_back(from[n][k]);
		k--;
		n = all.back();
	}
	reverse(all.begin() , all.end());
	for(auto u : all)
		cout << u << " ";
	cout << endl;
	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