Submission #854485

#	Time	Username	Problem	Language	Result	Execution time	Memory
854485		parsadox2	Split the sequence (APIO14_sequence)	C++14	22 / 100	2049 ms	45004 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 2 , K = 1e2 + 2;
int n , k , from[N][K] , a[N] , p[N];
long long dp[N][2] , A[N];

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];
	//dp[i][j] = (psum[i] - psum[ii]) * psum[ii] + dp[ii][j - 1];
	//dp[i][j] = psum[i] * psum[ii] + (psum[ii] ^ 2 + dp[ii][j - 1]) => A[ii];
	//dp[i][j] = psum[i] * psum[ii] + A[ii];
	for(int j = 2 ; j <= k ; j++)
	{
		int now = (j & 1) , prv = now ^ 1;
		set <pair<int , int>> st;
		dp[1][now] = 0;
		A[1] = -1LL * p[1] * p[1];
		st.insert({2 , 1});
		for(int i = 2 ; i <= n ; i++)
		{
			auto noww = *st.begin();
			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;
			st.erase(noww);
			if(st.empty() || (*st.begin()).first > noww.first + 1)
				st.insert(make_pair(noww.first + 1 , noww.second));
			int las = n + 1;
			while(!st.empty())
			{
				auto it = st.end();  it--;
				noww = *it;
				if(Add(noww.first , i) > Add(noww.first , noww.second))
				{
					st.erase(noww);
					las = noww.first;
					continue;
				}
				int low = noww.first , high = las;
				while(high - low > 1)
				{
					int mid = (low + high) >> 1;
					if(Add(mid , i) > Add(mid , noww.second))
						high = mid;
					else
						low = mid;						
				}
				las = high;
				break;
			}
			//cout << i << " " << las << endl;
			if(las != n + 1)
				st.insert({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: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29