Cod sursa(job #479059)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 22 august 2010 14:30:32
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <cstdio>
#include <algorithm>

using namespace std;

int n,i,j,Best[100000],maxim,aux;
struct interval
{
	int x,y;
}
a[110000];


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

int cmp(interval a, interval b)
{
	if (a.y<b.y)
		return 1;
	if(a.y>b.y)
		return 0;
	if(a.x<b.x)
		return 1;
	return 0;

}

int main()
{
    freopen("heavymetal.in","rt",stdin);
    scanf("%d", &n);
     for (i=1;i<=n;++i)
      {
         scanf("%d %d", &a[i].x,&a[i].y);
        maxim=max(maxim,a[i].y);
        }
	 sort(a+1,a+n+1,cmp);
	 j=1;
    for (i=1;i<=maxim;++i)
          {    
            Best[i]=Best[i-1];   
             while(i==a[j].y)
	    	{
			   aux=Best[a[j].x]+a[j].y-a[j].x;
			if(aux>Best[i])
				Best[i]=aux;
			j++;
		}

}

freopen("heavymetal.out","wt",stdout);
printf("%ld", Best[maxim]);
return 0;
}