Submission #37897

#	Time	Username	Problem	Language	Result	Execution time	Memory
37897		MatheusLealV	Split the sequence (APIO14_sequence)	C++14	11 / 100	2000 ms	86784 KiB

sequence

#include <bits/stdc++.h>
#define N 100005
#define K 202
#define inf 200000000000000000LL
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
 
int n, k, r, block[N], qtd, prox[N][K], e;
 
ll dp[N][3], sum[N];

ll A[N], B[N], ID[N];
 
inline void fastscan(int &number)
{
    register int c;
 
    number = 0;
 
    c = getchar();
 
    for (; (c>47 && c<58); c=getchar())
        number = number *10 + c - 48;
}
 
inline void fast_ll(ll &number)
{
    register int c;
 
    number = 0;
 
    c = getchar();
 
    for (; (c>47 && c<58); c=getchar())
        number = number *10 + c - 48;	
}
 
inline void addline(pair<pii, int> l)
{
	if(e && A[e - 1] == l.f.f)
	{
		if(B[e - 1] < l.f.s) return;
 
		if(B[e - 1] == l.f.s && ID[e - 1] < l.s) return;
 
		A[e - 1] = l.f.f, B[e - 1] = l.f.s, ID[e - 1] = l.s;
 
		return;
	}

	while(e >= 2 && (B[e - 2] - l.f.s) * (A[e - 1] - A[e - 1]) <= 
		(B[e - 1] - B[e - 2]) * (l.f.f - A[e - 1])) e--;

	e++;

	A[e - 1] = l.f.f, B[e - 1] = l.f.s, ID[e - 1] = l.s;
}
 
inline pair<ll, int> query( int x)
{	 
	if(r >= e) r = e - 1;
 
	while(r < e - 1 && A[r]*x + B[r] > A[r + 1]*x + B[r + 1])r++;
 
	return pii(A[r]*x + B[r], ID[r]);
}
 
int32_t main()
{
	//ios::sync_with_stdio(false); cin.tie(0);
 
	fastscan(n), fastscan(k);
 
	for(int i = 1; i <= n; i++) fast_ll(sum[i]), sum[i] += sum[i - 1];
 
	for(int i = 0; i <= n; i++) dp[i][0] = 0;
 
	for(int i = 0; i <= k; i++) dp[n][i] = 0;
 
	int A = 1, B = 0;
 
	for(int q = 1; q <= k ; q++)
	{
		e = 0;
 
		for(int i = n - 1; i >= 1; i--)
		{
			addline(make_pair(pii( -sum[i], -(sum[i]*sum[n] - sum[i]*sum[i] + dp[i + 1][ B ] )), i));
 
			pair<ll, int> best = query(sum[i - 1]);
 
			dp[i][A] = -best.f - sum[i - 1]*sum[n];
 
			prox[i][q] = best.s;
		}

		swap(A, B);
	}
 
	printf("%lld\n", dp[1][k%2]);
 
	int ini = 1, q = k;
 
	while(true)
	{
		if(!prox[ini][q]) break;
 
		qtd ++;
 
		block[prox[ini][q]] = 1;
 
		printf("%d ", prox[ini][q]);
 
		ini = prox[ini][q] + 1;
		
		q --;
	}
 
	int extra = k - qtd;
 
	for(int i = 1, cnt = 0; i <= n && cnt < extra; i++)
	{
		if(!block[i]) printf("%d ", i), cnt ++;
	}
 
	cout<<"\n";
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29