Cod sursa(job #87033)

Utilizator mugurelionutMugurel-Ionut Andreica mugurelionut Data 26 septembrie 2007 12:28:25
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.99 kb
#include <stdio.h>
#include <string.h>

#define NMAX 131072
#define LLINF 100000000000000000

#define BIGINT long long
#define fmt "%lld"

BIGINT f[NMAX], c[NMAX], s[NMAX], sp[NMAX], d[NMAX], dp[NMAX], p[NMAX];
BIGINT finit[NMAX], cmin[NMAX], sum;
int idx[2 * NMAX], le[2 * NMAX], ri[2 * NMAX];
int i, j, k, l, r, N, S, T;
//BIGINT cmin[NMAX], csto, dsum, x, y;

BIGINT get_min(int i)
{
	BIGINT v, vmin = LLINF;
	int nod;

	nod = NMAX + i - 1;

	while (nod > 0)
	{
		if (idx[nod] == 0)
			v = LLINF;
		else
			v = finit[idx[nod]] + p[idx[nod]] * (dp[i] - dp[idx[nod] - 1]);

		if (v < vmin)
			vmin = v;

		nod >>= 1;
	}

	return vmin;
}

void find_interval(int i, int& l, int& r)
{
	int li, ls, mid;
	BIGINT vmin1, vmin2, vi1, vi2, dv1, dv2;

	// binary search for the left end point (with "derivatives")

	li = i; ls = N; l = N + 2;

	while (li <= ls)
	{
		mid = (li + ls) / 2;

		vmin1 = get_min(mid);
		vmin2 = get_min(mid + 1);

		vi1 = finit[i] + p[i] * (dp[mid] - dp[i - 1]);
		vi2 = finit[i] + p[i] * (dp[mid + 1] - dp[i - 1]);

		dv1 = vi1 - vmin1;
		dv2 = vi2 - vmin2;

		if (dv1 < 0)
		{
			l = mid;
			ls = mid - 1;
		}
		else
		if (dv1 - dv2 > 0)
			li = mid + 1;
		else
			ls = mid - 1;
	}

	// binary search for the right end point (with "derivatives")

	li = l; ls = N + 1; r = 0;

	while (li <= ls)
	{
		mid = (li + ls) / 2;

		vmin1 = get_min(mid);
		vmin2 = get_min(mid + 1);

		vi1 = finit[i] + p[i] * (dp[mid] - dp[i - 1]);
		vi2 = finit[i] + p[i] * (dp[mid + 1] - dp[i - 1]);

		dv1 = vi1 - vmin1;
		dv2 = vi2 - vmin2;

		if (dv1 < 0)
		{
			r = mid;
			li = mid + 1;
		}
		else
		if (dv1 - dv2 > 0)
			li = mid + 1;
		else
			ls = mid - 1;
	}
}

void update(int l, int r, int i, int nod)
{
	int fs, fd;

	if (le[nod] == l && ri[nod] == r)
		idx[nod] = i;
	else
	{
		fs = (nod << 1);
		fd = (nod << 1) + 1;

		if (r < le[fd])
			update(l, r, i, fs);
		else
		if (l > ri[fs])
			update(l, r, i, fd);
		else
		{
			update(l, ri[fs], i, fs);
			update(le[fd], r, i, fd);
		}
	}
}

void init_tree(int nod)
{
	int fs, fd;

	if (nod < NMAX)
	{
		fs = (nod << 1);
		fd = (nod << 1) + 1;

		le[fs] = le[nod];
		ri[fs] = (le[nod] + ri[nod]) / 2;

		le[fd] = ri[fs] + 1;
		ri[fd] = ri[nod];

		init_tree(fs);
		init_tree(fd);
	}
}

int main()
{
	int T;

	le[1] = 1;
	ri[1] = NMAX;

	init_tree(1);

	freopen("branza.in", "r", stdin);

	scanf("%d %d %d", &N, &S, &T);

	memset(idx, 0, sizeof(idx));

	for (i = 1; i <= N; i++)
	{
		f[i] = 0;
		scanf(fmt, &c[i]);
		s[i] = S;
		scanf(fmt, &d[i]);
	}

	// compute sp and dp (partial sums)

	sp[0] = dp[0] = 0;
		
	for (i = 1; i <= N; i++)
		sp[i] = s[i] + sp[i - 1],
		dp[i] = d[i] + dp[i - 1];

	dp[N + 1] = dp[N] + 1;

	// dynamic programming

	cmin[0] = 0;

	for (i = 1; i <= N; i++)
	{
		p[i] = c[i] - sp[i - 1];
		finit[i] = cmin[i - 1] + f[i];

		find_interval(i, l, r);

		if (l <= r)
			update(l, r, i, 1);

		cmin[i] = get_min(i);

	}

	sum = 0;

	for (i = 1; i <= N; i++)
		sum += d[i] * sp[i - 1];

	freopen("branza.out", "w", stdout);
	printf(fmt, cmin[N] + sum);
	printf("\n");

	return 0;
}