Cod sursa(job #282850)

Utilizator MciprianMMciprianM MciprianM Data 18 martie 2009 13:38:08
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include<fstream>
#include<algorithm>
using namespace std;
#define MAXN 100001
struct Interval{
  int a, b;
};
Interval A[MAXN];
int best[MAXN];
int n;
bool cmp(Interval a1, Interval a2){
  return ( ( a1.b ) < ( a2.b ) ) ;
}

inline int max(int (a), int (b)){
  return ( a ) > ( b ) ? (  a ) : ( b ) ;
}
int searci(int x){
  int i, pas;
  for(pas=1;pas<=x;pas<<=1);
  for(i=0;pas;pas>>=1)
    if(i+pas<x&&A[i+pas].b<=A[x].a)
      i+=pas;
  return i;
}
int main(){
  int i;
  ifstream f("heavymetal.in");
  f>>n;
  A[0].a=A[0].b=0;
  for(i=1;i<=n;i++)
  	f>>A[i].a>>A[i].b;
  f.close();
  sort(A, A+n+1, cmp);
  for(i=1;i<=n;i++)
    best[i]=best[searci(i)]+(A[i].b-A[i].a);
  ofstream g("heavymetal.out");
  int maxim=-1;
  for(i=0;i<=n;i++)
    maxim=max(maxim, best[i]);
  g<<maxim<<'\n';
  g.close();
  return 0;
}