Cod sursa(job #183844)

Utilizator katakunaCazacu Alexandru katakuna Data 22 aprilie 2008 17:40:35
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include<stdio.h>   
#include<algorithm>
using namespace std;
  
int val,u,mij,sol,v[100001],n,i,k,c,p;   
  
  
struct heavy{int a,b;};   
heavy s[100001],aux;   


int cmp(heavy a,heavy b){
return a.b<b.b;
}
  
  
  
  
int main(){   
  
FILE *f=fopen("heavymetal.in","r");   
fscanf(f,"%d",&n);   
  for(i=1;i<=n;i++){   
  fscanf(f,"%d %d",&s[i].a,&s[i].b);   
  }   
fclose(f);   
  
k=n+1;
sort(s+1,s+k,cmp);

  
  for(i=1;i<=n;i++){   
  val=s[i].a;   
  v[i]=v[i-1];   
  p=0;   
  u=i;   
  
     while(p<=u){   
     mij=(p+u)/2;   
  
       if(s[mij].b<=val)   
       p=mij+1;   
  
       else  
       u=mij-1;   
  
  
     }   
  
  if( (v[u]+(s[i].b-s[i].a)) > v[i] )   
  v[i]=v[u]+(s[i].b-s[i].a);   
  
  }   
  
  
  
FILE *g=fopen("heavymetal.out","w");   
fprintf(g,"%d",v[n]);   
fclose(g);   
  
return 0;   
}