Cod sursa(job #185427)

Utilizator drag0shSandulescu Dragos drag0sh Data 25 aprilie 2008 12:58:44
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 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;
}
long B[MAX],poz[MAX];
int main(){
  citire();
  freopen("heavymetal.out","w",stdout);
  sort(a+1,a+n,functie);
  long i,j,prec;
  B[1]=a[1].y-a[1].x;
  poz[1]=0;
  for(i=2;i<n;++i){
        if(a[i-1].y<=a[i].x) {poz[i]=i-1;j=i-1;}
        else{
            j=poz[i-1];
            while(a[j].y>a[i].x)j=poz[j];
            poz[i]=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;
}