Cod sursa(job #151802)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 8 martie 2008 17:25:48
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 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);
	for(i=0;i<n;++i)
	{
		if(v[i].a>=v[i-1].b)
		{
			w[i].cost=v[i].b-v[i].a;
			w[i].ora=v[i].b;
			sa+=w[i].cost;
			//printf("          ");
		}	
		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);
			s=0;
			for(k=j+1;k<i;++k)
				s+=w[k].cost;
			//printf(" %d ",s);
			if(v[i].b-v[i].a>s)
			{
				for(k=j+1;k<i;++k)
				{
					w[k].cost=0;
					w[k].ora=w[k-1].ora;
				}
				//printf(" d");
				w[i].cost=v[i].b-v[i].a;
				w[i].ora=v[i].b;
				sa=w[i].cost;
			}
			else
			{
				w[i].cost=0;
				w[i].ora=w[i-1].ora;
			}	
		
		}
		
		//printf("%d %d ",v[i].a,v[i].b);
		//printf(" %d %d",w[i].cost,w[i].ora);
		//printf(" %d ",sa);
		//printf("\n");
	}
	
	for(i=0;i<n;++i)
	{
		rez+=w[i].cost;
		//printf("%d %d  %d %d\n",v[i].a,v[i].b,w[i].cost,rez);
	}	
	printf("%d\n", rez);	
	return 0;
}