Cod sursa(job #339312)

Utilizator iulia609fara nume iulia609 Data 9 august 2009 13:16:06
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 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)   
{   
    return a > b ? a : b;   
}   
  
int part(int in, int sf)
{
	int x,aux,p,i,j;
	p = in;
	//p = (rand()%(sf-in)+in);
	x = B[V[p]];
	i = p;
	
	for(j = p+1; j <= sf; j++)
		if(B[V[j]] <= x)
			{
				i++;
				aux = V[i], V[i] = V[j], V[j] = aux;
			}
	aux = V[p], V[p] = V[i], V[i] = aux;
	return i;
}


void qsort(int in, int sf)
{ int q;
	if(in < sf)
		{
			q = part(in, sf);
			qsort(in, q-1);
			qsort(q+1, 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];   
              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]]));  
				   else if(B[V[j]] > B[V[i]]) break;
                    
                k = B[V[i]];   
          }   
         
      fprintf(g, "%d\n", Be[T]);   
         
         
      fclose(f);   
      fclose(g);   
      return 0;   
}