Cod sursa(job #351402)

Utilizator borsoszalanBorsos Zalan borsoszalan Data 27 septembrie 2009 22:49:48
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include<stdio.h>
#include<stdlib.h>

int n,j,i;
struct asd{int v; int k; long best;};
asd a[100006];

int cmp(const void *x, const void *y)
{return ((asd *)x)->v-((asd *)y)->v;}

int main()
{
	freopen("heavymetal.in", "r", stdin);
	freopen("heavymetal.out", "w", stdout);
	scanf("%d", &n);
	for(i=1;i<=n;i++)
		scanf("%d %d", &a[i].k, &a[i].v);
	qsort(a, n+1, sizeof(asd), cmp);
	for(i=1;i<=n;i++)
	{
		a[i].best=a[i-1].best;
		for(j=i-1;j>=1&&a[j].v>a[i].k;j--);
		if(a[i].best<a[j].best+a[i].v-a[i].k)
			a[i].best=a[j].best+a[i].v-a[i].k;
	}
	printf("%ld\n", a[n].best);
	return 0;
}