Cod sursa(job #339147)

Utilizator iulia609fara nume iulia609 Data 8 august 2009 14:56:30
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include<stdio.h>
#include<algorithm>
#include<cstdlib>
#define dim 100001
using namespace std;

int Be[dim], A[dim], B[dim];
int V[dim];

int max(int a, int b)
{
	if(a > b) return a;
	return b;
}


void qsort(int inc, int sf)
{
	int i,j,temp, aux;
	i = inc;
	j = sf;
	temp = B[V[rand()%(j-i+1)+i]];
	
	do
	  {	while(B[V[i]] < temp) i++;
		while(B[V[j]] > temp) j--;
		  if(i < j) aux = V[i], V[i] = V[j], V[j] = aux;
		  if(i <= j) j--, i++;
	  }	while (i <= j);

	if(inc < j) qsort(inc, j);
	if (i < sf) qsort(i, sf);
}




int main()
{ int T;
  int i,j,k,N,t;

	  FILE *f = fopen("heavymetal.in", "r");
	  FILE *g = fopen("heavymetal.out", "w");
	  
	  fscanf(f, "%d", &N);
	  
	  for(i = 1; i <= N; i++)
		  {
			  fscanf(f, "%d%d", &A[i], &B[i]);
			  V[i] = i;
		  }
	  
	  qsort(1, N);
	  
	  T = B[V[N]];
	  
	  k = 1;
	  for(i = 1; i <= N; i++)
		  {
			  for(t = k+1; t <= B[V[i]]; t++)
				  Be[t] = Be[t-1];
			  //while(B[V[k]] < i) k++;
			  //if(B[V[k]] == i)
				  //{
					  //Be[i] = Be[i-1];
					  for(j = 1; j <= N; j++)
						 if(B[V[j]] == B[V[i]])
						    Be[B[V[i]]] = max(Be[B[V[i]]], Be[A[V[j]]] + (B[V[j]] - A[V[j]]));
				  //}
				k = B[V[i]];
		  }
	  
	  fprintf(g, "%d\n", Be[T]);
	  
	  
	  fclose(f);
	  fclose(g);
	  return 0;
}