Submission #26419

#	Time	Username	Problem	Language	Result	Execution time	Memory
26419		zscoder	Split the sequence (APIO14_sequence)	C++14	71 / 100	2000 ms	86164 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

struct line
{
	ll m, c; int idx;
	ll val(ll x)
	{
		return (m*x + c);
	}
};

int n, k;

const int N = 1e5 + 3;
const int K = 202;

ll dp[N][2];
int par[N][K];
ll s[N];

line hull[N];
int siz;
int ptr; 

bool bad(int cur, int prev, int nxt)
{
	line x, y, z;
	y = hull[cur];
	x = hull[prev];
	z = hull[nxt];
	return (y.c - x.c)*(y.m - z.m) >= (z.c - y.c)*(x.m - y.m);
}

void add(ll a, ll b, int id)
{
	line n; n.m = a; n.c = b; n.idx = id; hull[siz++] = n;
	while(siz >= 3 && bad(siz - 2, siz - 3, siz - 1))
	{
		hull[siz-2] = hull[siz-1];
		siz--;
	}
}

ll query(ll x)
{
	if(ptr >= siz) ptr = siz - 1; 
	while(ptr < siz - 1 && hull[ptr].val(x) > hull[ptr+1].val(x))
	{
		ptr++;
	}
	return hull[ptr].val(x);
}

int a[N];

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> k;
	ll sum = 0;
	ll ans = 0;
	for(int i = 1; i <= n; i++) 
	{
		cin >> a[i];
		sum += a[i];
		s[i] = s[i-1] + a[i];
		dp[i][1] = s[i]*s[i];
	}
	for(int j = 2; j <= k + 1; j++)
	{
		for(int i = j; i <= n; i++)
		{
			ll x = -2*s[i-1];
			ll y = dp[i-1][(j+1)&1] + s[i-1]*s[i-1];
			add(x, y, i - 1);
			ll tmp = query(s[i]);
			dp[i][j&1] = tmp + s[i]*s[i];
			par[i][j] = hull[ptr].idx;
		}
		siz = 0; ptr = 0;
	}
	int idx = n;
	ans = dp[n][(k+1)&1];
	ans = sum*sum - ans;
	ans >>= 1;
	cout << ans << "\n";
	for(int i = k + 1; i >= 2; i--)
	{
		cout << par[idx][i] << " ";
		idx = par[idx][i];
	}
	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