Cod sursa(job #149828)

Utilizator znakeuJurba Andrei znakeu Data 6 martie 2008 09:38:42
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <stdio.h>
#include <stdlib.h>
#define MAXN 100001
struct wtf
{
	int s,e,v;
};

wtf V[MAXN];
int v[MAXN],n;

int cmp(const void *a, const void *b)
{
	wtf x=*(wtf*)a,y=*(wtf*)b;
	return x.e-y.e;
}

int ffs(int p)
{
	int k,i;
	k=V[p-1].v;
	if (v[p-1]>k)
		k=v[p-1];
	for (i=p-1; i>0; i--)
		if (V[i-1].e<=V[p-1].s)
		{
			if (k<v[i]+V[p-1].v)
				k=v[i]+V[p-1].v;
			i=0;
		}
	return k;
}

int main()
{
	FILE *in  = fopen("heavymetal.in","r");
	FILE *out = fopen("heavymetal.out","w");
	int i;
	
	fscanf(in,"%d",&n);
	for (i=0; i<n; i++)
	{
		fscanf(in,"%d%d",&V[i].s,&V[i].e);
		V[i].v=V[i].e-V[i].s;
	}
	qsort(V,n,sizeof(V[0]),cmp);
	
	v[0]=0; v[1]=V[0].v;
	for (i=2; i<=n; i++)
		v[i]=ffs(i);
	
	fprintf(out,"%d\n",v[n]);
	
	fclose(in);
	fclose(out);
	return 0;
}