Submission #443217

#	Time	Username	Problem	Language	Result	Execution time	Memory
443217		hivakarami	Split the sequence (APIO14_sequence)	C++14	100 / 100	1681 ms	82332 KiB

sequence

#include<bits/stdc++.h>

 
using namespace std;
 
typedef long long int ll;
typedef long double ld;
#define f first
#define s second
#define pb push_back
#define pii pair<int, int>

 
const int N = 100000 + 100;
const int K = 200 + 100;
const ll inf = 1e18;

ll ps[N], dp[N][2], a[N];
int op[K][N];

inline ll get(int l, int r)
{
	ll sum = ps[r] - ps[l];
	return (sum * (sum-1)) / 2;
}

void solve(int l, int r, int opl, int opr, int k)
{
	//cout << l << ' ' << r << ' ' << opl << ' ' << opr << endl;
	if(l >= r || opr < opl)
		return;
	
	int mid = (l + r) / 2;
	op[k][mid] = opl;
	for(int i = opl; i < min(mid, opr); i++)
	{
		if(dp[mid][1] > dp[i][0] + get(i+1, mid+1))
		{
			dp[mid][1] = dp[i][0] + get(i+1, mid+1);
			op[k][mid] = i;
		}
	}
	
	solve(l, mid, opl, op[k][mid]+1, k);
	solve(mid+1, r, op[k][mid], opr, k);
	
}



int main()
{
    
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);	

	int n, k;
	cin >> n >> k;
	k++;
	for(int i = 0; i < n; i++)
		cin >> a[i];
		
	for(int i = 1; i <= n; i++)
		ps[i] = ps[i-1] + a[i-1];	

	for(int i = 0; i < n; i++)
		dp[i][1] = get(0, i+1);
	
	for(int i = 2; i <= k; i++)
	{
		for(int j = 0; j < n; j++)
		{
			dp[j][0] = dp[j][1];
			dp[j][1] = inf;
		}
		solve(0, n, 0, n, i);
	}

	/*
	for(int j = 1; j <= k; j++)
		for(int i = 0; i < n; i++)
			cout << i << ' ' << j << ' ' << dp[i][j] << endl;
	*/
	
	cout << get(0, n) - dp[n-1][1] << endl;

	int i = n-1, j = k;
	while(j > 1)
	{
		cout << op[j][i] + 1 << ' ';
		//v.pb(op[i][j] + 1);
		i = op[j][i];
		j--;
	}
	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