Cod sursa(job #153780)

Utilizator abcabcIon Popescu abcabc Data 10 martie 2008 18:49:06
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <stdio.h>
#include <stdlib.h>
#define N 100012
struct timp
{
	int ora,cost;
};

struct interval
{
	 int a,b;
};	
int compar (const void*p, const void*q) 
{	
	interval *pp=(interval*)p, *qq=(interval*)q;
	interval x=*pp, y=*qq;
	if(x.b<y.b)
		return -1;
	if(x.b>y.b)
		return 1;
	return 0;	
}

int main()
{	interval v[N];
	timp w[N];
	int n,dr,i,j,k,s,sa=0,rez=0;
	freopen("heavymetal.in", "r", stdin);
	freopen("heavymetal.out", "w",stdout);
	scanf("%d", &n);
	for(i=0;i<n;++i)
		scanf("%d%d", &v[i].a, &v[i].b);
	qsort(v,n,sizeof(v[0]),compar);
	w[0].cost=v[0].b-v[0].a;
	w[0].ora=v[0].b;
	
	for(i=1;i<n;++i)
	{
		
		
		if(v[i].a>=v[i-1].b)
		{
			w[i].cost=(v[i].b-v[i].a)+w[i-1].cost;
			w[i].ora=v[i].b;
			//printf("normal %d %d %d\n ",v[i].b-v[i].a,w[i-1].cost,w[i].cost);
		}	
		else
		{
			for(j=i-1;j>=0;--j)
				if(v[j].b<=v[i].a)
					break;
			//printf("%d %d    ",v[j].b,v[i].a);
			if(v[i].b-v[i].a+w[j].cost>w[i-1].cost)
			{
				for(k=j+1;k<i;++k)
				{
					//printf(" k=%d ", k);
					w[k].cost=w[k-1].cost;
					w[k].ora=w[k-1].ora;
				
				}
				//printf(" \n");
				w[i].cost=(v[i].b-v[i].a)+w[j].cost;
				w[i].ora=v[i].b;
			}
			else
			{
				w[i].cost=w[i-1].cost;
				w[i].ora=w[i-1].ora;
			}	
		}
		//printf(" c=%d %d %d\n",w[i].cost,w[i].ora,i);
	}
	
	/*for(i=0;i<n;++i)
	{
		printf("%d %d %d ",i,v[i].a,v[i].b);
		printf(" %d %d",w[i].cost,w[i].ora);
		printf("\n");
	
	}*/
	rez=w[n-1].cost;
	printf("%d\n", rez);	
	return 0;
}