Cod sursa(job #138957)

Utilizator vlad.maneaVlad Manea vlad.manea Data 19 februarie 2008 15:41:24
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <stdio.h>
#define nmax 10005

struct interval
{
	int in, out;
};

int N, maxim, suma[nmax];

interval A[nmax], B[nmax];

int max(int i, int j)
{
	return i > j? i: j;
}

void msort(int l, int r)
{
	int i, j, k;

	if (l >= r) return;

	int m = (l+r)/2;

	msort(l, m);
	msort(m+1, r);

	for (i = k = l, j = m+1; i <= m && j <= r; ++k)
		if (A[i].out < A[j].out || A[i].out == A[j].out && A[i].in <= A[j].in)
			B[k] = A[i++];
		else
			B[k] = A[j++];

	while (i <= m)
		B[k++] = A[i++];

	while (j <= r)
		B[k++] = A[j++];

	for (i = l; i <= r; ++i)
		A[i] = B[i];
}

int binary(int l, int r, int value)
{
	if (l > r) return 0;
	int m = (l+r)/2;
	if (A[m].out <= value)
		return max(m, binary(m+1, r, value));
	else
		return binary(l, m-1, value);
}

int main()
{
	int i;

	freopen("heavymetal.in", "r", stdin);
	freopen("heavymetal.out", "w", stdout);

	scanf("%d", &N);

	for (i = 1; i <= N; ++i)
		scanf("%d%d", &A[i].in, &A[i].out);

	msort(1, N);

	for (suma[1] = A[1].out-A[1].in, i = 2; i <= N; ++i)
		suma[i] = max(A[i].out - A[i].in + suma[binary(1, N, A[i].in)], suma[i-1]);

	for (i = 1; i <= N; ++i)
		if (suma[i] > maxim)
			maxim = suma[i];

	printf("%d\n", maxim);

	return 0;
}