Submission #37895

#	Time	Username	Problem	Language	Result	Execution time	Memory
37895		MatheusLealV	Split the sequence (APIO14_sequence)	C++14	71 / 100	2000 ms	90660 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];

ll dp[N][3], sum[N];

void fastscan(int &number)
{
    register int c;

    number = 0;

    c = getchar();

    for (; (c>47 && c<58); c=getchar())
        number = number *10 + c - 48;
}

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 bool bad(pii A, pii B, pii C)
{
	pii r, s;

	r = A, s = C;

	double a = ((double)(r.s - s.s))/((double)(s.f - r.f));

	r = B, s = A;

	double b = ((double)(r.s - s.s))/((double)(s.f - r.f));

  return a >= b;
}

inline void addline(vector< pair<pii, int> > &line, pair<pii, int> l)
{
	if(line.size() && line.back().f.f == l.f.f)
	{
		if(line.back().f.s < l.f.s) return;

		if(line.back().f.s == l.f.s && line.back().s < l.s) return;

		line.pop_back();

		line.push_back(l);

		return;
	}

	while(line.size() >= 2 && bad( line[line.size() - 2].f, line.back().f, l.f )) line.pop_back();

	line.push_back(l);
}

inline pair<ll, int> query(vector< pair<pii, int> > &line, int x)
{	
	int p = line.size();

	if(r >= p) r = p - 1;

	while(r < p - 1 && line[r].f.f*x + line[r].f.s > line[r + 1].f.f*x + line[r + 1].f.s)r++;

	return pii(line[r].f.f*x + line[r].f.s, line[r].s);
}

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++)
	{
		vector< pair<pii, int> > line;

		for(int i = n - 1; i >= 1; i--)
		{
			addline(line, make_pair(pii( -sum[i], -(sum[i]*sum[n] - sum[i]*sum[i] + dp[i + 1][ B ] )), i));

			pair<ll, int> best = query(line, 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: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 0 / 29