Cod sursa(job #181247)

Utilizator fogabFodor Gabor fogab Data 18 aprilie 2008 06:03:10
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <stdio.h>
#include <iostream>
#include <fstream>

using namespace std;

int s[100000],f[100000],a[100000],sol[100001];
int N;

int binary_search(int val)  
{  
    int i, step;  
    for (step = 1; step < N; step <<= 1);  
    for (i = 0; step; step >>= 1)  
        if (i + step < N && f[a[i + step]] <= val)  
           i += step;  
    return i;  
} 

void quicksort (int a[], int lo, int hi)
{

    int i=lo, j=hi, h;
    int x=f[a[lo+rand()%(hi-lo+1)]];

    do
    {    
        while (f[a[i]]<x) i++; 
        while (f[a[j]]>x) j--;
        if (i<=j)
        {
            h=a[i]; a[i]=a[j]; a[j]=h;
            i++; j--;
        }
    } while (i<=j);

    if (lo<j) quicksort(a, lo, j);
    if (i<hi) quicksort(a, i, hi);
}

int main(void){
    
    ifstream  in("heavymetal.in" );
    ofstream out("heavymetal.out"); 
    
    int i,j,max = 0;
    
    in >> N;
    
    for (int i=0;i<N;i++){
        in >> s[i] >> f[i];
        
        a[i] = i;
        }
    
    quicksort(a,0,N-1);             
    
    for (int i=0;i<N;i++){
        int find =  binary_search(s[a[i]]);
        if (find == 0 && f[a[0]] > s[a[i]]) find = -1;
        int pr = sol[find+1] + f[a[i]] - s[a[i]];
        if (sol[i] > pr) pr = sol[i];
        sol[i+1] = pr;
        //cout << sol[i+1] << " ";        
        if (sol[i+1] > max) max = sol[i+1];
        }
    
    //cin >> N;
    
    out << max;
    
    in.close();            
    out.close();        
    
    return 0;    
}