Submission #443195

#	Time	Username	Problem	Language	Result	Execution time	Memory
443195		hivakarami	Split the sequence (APIO14_sequence)	C++14	71 / 100	142 ms	131076 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 = 2e5 + 100;
const int K = 200 + 100;
const ll inf = 1e18;

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

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;

	if(l + 1 == r)
	{
		int mid = l;
		op[mid][k] = opl;
		for(int i = opl; i < min(mid, opr); i++)
		{
			if(dp[mid][k] > dp[i][k-1] + get(i+1, mid+1))
			{
				dp[mid][k] = dp[i][k-1] + get(i+1, mid+1);
				op[mid][k] = i;
			}
		}
		return;
	}
	
	
	int mid = (l + r) / 2;
	op[mid][k] = opl;
	for(int i = opl; i < min(mid, opr); i++)
	{
		if(dp[mid][k] > dp[i][k-1] + get(i+1, mid+1))
		{
			dp[mid][k] = dp[i][k-1] + get(i+1, mid+1);
			op[mid][k] = i;
		}
	}
	
	solve(l, mid, opl, op[mid][k]+1, k);
	solve(mid+1, r, op[mid][k], 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 j = 0; j <= k; j++)
			dp[i][j] = inf;
	}
		
	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++)
		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 << dp[n-1][1] - dp[n-1][k] << endl;

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