Cod sursa(job #1223060)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 25 august 2014 13:06:48
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<fstream>
#include<algorithm>
using namespace std;
typedef struct { int x,y; } tip;
tip a[100005];
int i,j,n,sol[100005];

bool cmp(tip a, tip b) {
   if (a.x!=b.x) return a.x<b.x;
   return a.y<b.y;     
}

int main(void) {
   ifstream fin("heavymetal.in");
   ofstream fout("heavymetal.out");
   
   fin>>n;
   
   for (i=1; i<=n; ++i) fin>>a[i].x>>a[i].y;
   
   sort(a+1,a+n+1,cmp);   
   
   sol[n]=a[n].y-a[n].x;
   
   for (i=n-1; i>=1; --i) {
       int l=i+1,r=n;
       
       while (l<=r) {
             int mid=(l+r)/2;
             
             if (a[mid].x<a[i].y) l=mid+1;
             else r=mid-1;
             
             }
       
       sol[i]=max(sol[i+1],a[i].y-a[i].x+sol[l]);
       
       }
       
   fout<<sol[1];
    
   return 0; 
}