Cod sursa(job #384168)

Utilizator rayvianPricope Razvan rayvian Data 19 ianuarie 2010 14:27:16
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

#define FILE_IN "heavymetal.in"
#define FILE_OUT "heavymetal.out"


const int SIZE=100000;

int n;
struct pConcerte
{
  int inc;
  int sf;

  bool operator > (const pConcerte &c)
  {
    return (this->sf > c.sf);
  }
  bool operator < (const pConcerte &c)
  {
    return (this->sf < c.sf);
  }
  bool operator == (const pConcerte &c)
  {
    return (this->sf == c.sf);
  }
}v[SIZE];

void merge_sort(int start,int end)
{
  if(start==end)
    return ;

  int mid=start+(end-start)/2;
  merge_sort(start,mid);
  merge_sort(mid+1,end);

  int p1=start;
  int p2=mid+1;
  int poz_a=0;
  pConcerte *a=new pConcerte[end-start+1];

  while( (p1<=mid) && (p2<=end) )
  {
    if( v[p1] < v[p2] )
      a[poz_a++]=v[p1++];
    else if( v[p2] < v[p1] )
      a[poz_a++]=v[p2++];
    else if( v[p2]== v[p1] )
    {
     a[poz_a++]=v[p2++];
     a[poz_a++]=v[p1++];
    }
  }

  if(p1<=mid)
    for(int i=p1; i<=mid; i++)
      a[poz_a++]=v[i];
  if(p2<=end)
    for(int i=p2; i<=end; i++)
      a[poz_a++]=v[i];

  poz_a=0;
  for(int i=start; i<=end; i++)
    v[i]=a[poz_a++];

  delete []a;

}

inline int max(int a,int b)
{
	return (a>b?a:b);
}



int Lung[11];
int main()
{
  freopen(FILE_IN,"r",stdin);
	freopen(FILE_OUT,"w",stdout);
  scanf("%d",&n);
  for(int i=1; i<=n; i++)
    scanf("%d %d",&v[i].inc,&v[i].sf);


  merge_sort(1,n);

	
	int itr=1;
	for(int i=1; i<=v[n].sf; i++)
	{
		Lung[i]=Lung[i-1];
		while(v[itr].sf==i)
		{
			Lung[i]=max(Lung[i],Lung[v[itr].inc]+v[itr].sf-v[itr].inc);
			itr++;
		}
	}
	printf("%d",Lung[v[n].sf]);

  return 0;
}