Cod sursa(job #586505)

Utilizator bugyBogdan Vlad bugy Data 2 mai 2011 09:54:19
Problema Heavy metal Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<stdio.h>
#define dim 100005 
using namespace std;

int n,i,j,a[dim],b[dim],max,best[dim];

void sort(int in,int sf)
{
int i,j,temp,aux;
i=in;
j=sf;
temp=b[(i+j)/2];

while(i<=j)
{
	while(b[i]<temp) i++;
	while(b[j]>temp) j--;
	
	if(i<=j)
	{
		aux=b[i]; b[i]=b[j]; b[j]=aux;	
		aux=a[i]; a[i]=a[j]; a[j]=aux;	
	}
	if(i<=j)
		i++,j--;
}

if(in<=j) sort(in,j);
if(i<=sf) sort(i,sf);

}

int main()
{
	FILE *f=fopen("heavymetal.in","r") , *g=fopen("heavymetal.out","w");
	
fscanf(f,"%d",&n);


for(i=1;i<=n;i++)
	fscanf(f,"%d %d",&a[i],&b[i]);

sort(1,n);


for(i=1;i<=n;i++)
{
	
	for(j=i-1;j>0;j--)
	{
		if( a[i] > b[j] )
			if ( ( best[j] + b[i]-a[i] ) > best[i])
				best[i] = ( best[j] + b[i]-a[i] ) ;
	}
	if(best[i] < b[i]-a[i])
		best[i] = b[i]-a[i];
	
	if(best[i]>max)
		max=best[i];
}

fprintf(g,"%d\n",max);


fclose(f);
fclose(g);

return 0;
}