Cod sursa(job #145061)

Utilizator M@2Te4iMatei Misarca M@2Te4i Data 28 februarie 2008 12:37:47
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define v 100000

int n,a[2][v],best[v];

void citire()
{
	freopen("heavymetal.in","r",stdin);
	scanf("%d", &n);
	for (int i=1; i<=n; i++)
		scanf("%d%d", &a[0][i], &a[1][i]);
	fclose(stdin);
}

void quick(int st, int dr)
{
	int x,i,j,aux;
	x=a[1][(st+dr)/2];
	i=st;
	j=dr;
	do
	{
		while (a[1][i]<x)
			++i;
		while (a[1][j]>x)
			--j;
		if (i<=j)
		{
			aux=a[1][i];
			a[1][i]=a[1][j];
			a[1][j]=aux;
			aux=a[0][i];
			a[0][i++]=a[0][j];
			a[0][j--]=aux;
		}
	}
	while (i<=j);
	if (st<j)
		quick(st,j);
	if (i<dr)
		quick(i,dr);

}

void rezolvare()
{
	int q=0;
	for (int i=1; i<=n; i++)
	{
//		q=best[i-1];
		if (q<best[a[0][i]]+(a[1][i]-a[0][i]))
			q+=best[a[0][i]]+(a[1][i]-a[0][i]);
		best[i]=q;
	}
}

int main()
{
	citire();
	freopen("heavymetal.out","w",stdout);
	quick(1,n);
	rezolvare();
	printf("%d", best[n]);
	fclose(stdout);
	return 0;
}