Cod sursa(job #185430)

Utilizator drag0shSandulescu Dragos drag0sh Data 25 aprilie 2008 13:03:10
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <algorithm>
using namespace std;
#include <stdio.h>
#define MAX 100001
struct smen{
    long x,y;
};
smen a[MAX];
long n;
void citire(){
 freopen("heavymetal.in","r",stdin);
 long i;
 scanf("%ld",&n);
 ++n;
 for(i=1;i<n;++i)
     scanf("%ld %ld",&a[i].x,&a[i].y);
fclose(stdin);
}
long functie(smen a,smen b){
    return a.y<b.y;
}
int main(){
  citire();
  freopen("heavymetal.out","w",stdout);
  sort(a+1,a+n,functie);
  long i,B[MAX],j,prec;
  B[1]=a[1].y-a[1].x;
  for(i=2;i<n;++i){
        j=i-1;
        while(a[j].y>a[i].x)j--;
        prec=B[j]+a[i].y-a[i].x;
        B[i]=B[i-1]>prec?B[i-1]:prec;
    }
    printf("%ld",B[n-1]);
    return 0;