Cod sursa(job #520935)

Utilizator akumariaPatrascanu Andra-Maria akumaria Data 10 ianuarie 2011 20:07:31
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include<stdio.h>
#include<stdlib.h>

struct bob
{int a,b;};


int comp(const void *a,const void*b)
{
	bob *x,*y;
	x=(bob*)a;
	y=(bob*)b;
	if(x->b-y->b==0)
		return 0;
	if(x->b-y->b>0)
		return 1;
	return -1;
}


int c[10010];
bob v[100010];


int main()
{
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
	int n,i,gasit,nr=0;
	scanf("%d",&n);
	for(i=1;i<=n;++i)
		scanf("%d%d",&v[i].a,&v[i].b);
	qsort(v+1,n,sizeof(v[0]),comp);
	for(i=1;i<=v[n].b;++i)
	{
		c[i]=c[i-1];
		gasit=0;
		while(!gasit)
		{
			if(v[++nr].b==i&&v[nr].b-v[nr].a+c[v[nr].a]>c[i])
			{
				c[i]=v[nr].b-v[nr].a+c[v[nr].a];
				gasit=0;
			}
			else
				if(v[nr].b>i)
				{
					--nr;
					break;
				}
		}
	}
	printf("%d\n",c[v[n].b]);
	return 0;
}