Cod sursa(job #138366)

Utilizator marius135Dumitran Adrian Marius marius135 Data 18 februarie 2008 14:17:32
Problema Heavy metal Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include<stdio.h>
#include<stdlib.h>

struct timp{long timp,fel,interv,dist;};
long n;
timp v[1024*128 *2];
long x[1024*128];

int cmpstruct ( const void *a, const void *b)
{
	timp c = *(timp *)a, d= *(timp *)b;
	
	if( c.timp != d.timp)
		return c.timp-d.timp;
	else return c.fel- d.fel;
	
}

int main()
{
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
	
	scanf("%ld",&n);
	for(long  i = 1; i <= n; ++i)
	{
		long a,b;
		scanf("%ld %ld",&a,&b);
		v[i*2-1].timp = a;
		v[i*2-1].fel = 1;
		v[i*2-1].interv = i;
		v[i*2-1].dist = b-a;
		v[i*2].timp = b;
		v[i*2].interv = i;
	}
	
	qsort(v+1,2*n,sizeof(v[0]),cmpstruct);
	
	long max = 0;
	for(long  i = 1; i <= 2*n; ++i)
	{
		if( v[i].fel == 1)// intrare
		{
			x[v[i].interv] = max+ v[i].dist;
		}
		else
		{
			if(x[v[i].interv] > max)
				max = x[v[i].interv];
		}
	}
	
	printf("%ld\n",max);
	
	return 0;
}