Cod sursa(job #184102)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 23 aprilie 2008 00:42:06
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <stdio.h>
#include <stdlib.h>

int n, ord[1000000], best[1000000], maxim;

typedef struct
{
	int a, b;
} interval;
interval a[100000], b[100000];

int max (int x, int y) { return x > y ? x : y; }

int cmp(const void *p, const void *q)
{
	int x = *(int*)p, y = *(int*)q;
	if (a[x].b == a[y].b) return a[x].a - a[y].a;
	return a[x].b - a[y].b;
}

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

	int i;
	scanf("%d",&n);
	for (i = 0; i < n; i++)
	{
		scanf("%d %d",&a[i].a,&a[i].b);
		ord[i] = i;
	}

	qsort(ord, n, sizeof(int), cmp);

	for (i = 1; i <= n; i++) b[i] = a[ ord[i-1] ] ;
	for (i = 1; i <= n; i++) ord[i] = i;
}

int main()
{
	int i, j, x, aux;
	citire();

	x = b[n].b; j = 1;
	for (i = 1; i <= x; i++)
	{
		best[i] = best[i - 1];
		while(i == b[j].b)
		{
			aux = best[b[j].a] + b[j].b - b[j].a;
			if(aux > best[i]) best[i] = aux;
			j++;
		}
		if (best[i] > maxim) maxim = best[i];
	}
	printf("%d\n",maxim);
	return 0;
}