Submission #37881

#	Time	Username	Problem	Language	Result	Execution time	Memory
37881		MatheusLealV	Split the sequence (APIO14_sequence)	C++14	0 / 100	0 ms	1840 KiB

sequence

#include <bits/stdc++.h>
#define int long long
#define N 100005
#define K 202
#define inf 2000000000000000
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;

int n, k, v[N], dp[N][K], sum[N], prox[N][K], r;

vector< pair<pii, int> > line;

int F(int x, int id)
{
	return line[id].f.f*x + line[id].f.s;
}
double intersect(pii r, pii s)
{
  return ((double)(r.s - s.s))/((double)(s.f - r.f));
}

bool bad(pii A, pii B, pii C)
{
  return intersect(A, C) >= intersect(B, A);
}

void addline(pair<pii, int> l)
{
	if(line.size()&&line.back().f.f == l.f.f)
	{
		if(line.back().f.s < l.f.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);
}

pii query(int x)
{
	pii best = pii(inf, -1);

	//for(auto l: line) best = min(best, pii(l.f.f*x + l.f.s, l.s)), cout<<l.f.f<<"\n";

	//return best;

	int p = line.size();
	if(r >= p) r = p - 1;
	while(r < p - 1 && F(x, r) > F(x, r + 1))r++;
	return pii(F(x, r), line[r].s);
}

pii query_Hull(int x) 
{
    int ini = 0, fim = line.size() - 1, mid, best = -1;

    while(fim >= ini)
    {
        mid = (ini + fim)/2;

        double pos = mid > 0? intersect(line[mid].f, line[mid - 1].f) : - inf;

        if(pos <= x) best = mid, ini = mid + 1;

        else fim = mid - 1; 
    }

    return pii((best == -1 ? inf : line[best].f.f*x + line[best].f.s), line[best].s);
}

void print(int ini, int k)
{
	if(!prox[ini][k]) return;

	cout<<prox[ini][k]<<" ";

	print(prox[ini][k] + 1, k - 1);
}

int32_t main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n>>k;

	for(int i = 1; i <= n; i++) cin>>v[i], sum[i] = sum[i - 1] + v[i];

	for(int i = 0; i <= n; i++) dp[i][0] = 0;

	for(int i = 0; i <= k; i++) dp[n][i] = 0;

	for(int q = 1; q <= k ; q++)
	{
		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][q - 1] )), i));
			
			pii best = query(sum[i - 1]);

			dp[i][q] = -best.f - sum[i - 1]*sum[n];

			prox[i][q] = best.s;
		}

		line.clear();

		r = 0;
	}

	cout<<dp[1][k]<<"\n";

	print(1, k);

	cout<<"\n";
}

Compilation message (stderr)

sequence.cpp: In function 'pii query(long long int)':
sequence.cpp:49:6: warning: variable 'best' set but not used [-Wunused-but-set-variable]
  pii best = pii(inf, -1);
      ^

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