Cod sursa(job #1312679)

Utilizator rangerChihai Mihai ranger Data 9 ianuarie 2015 20:46:00
Problema Heavy metal Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<fstream>
#include<algorithm>
#define max(a,b) a>b ? a : b
using namespace std;

ifstream cin("heavymetal.in");
ofstream cout("heavymetal.out");


const int N = 100003;

struct interval{
 int l,r;};
interval a[N];
int n,i;
long long best[N];

bool comp(interval i1,interval i2){
 return  ((i1.r < i2.r)||(i1.r==i2.r && i1.l>i2.l) ); }

int main()
{
    cin>>n;
    for (i=1;i<=n;i++)
        cin>>a[i].l>>a[i].r;
    sort(a+1,a+n+1,comp);

    best[1]=a[1].r-a[1].l;
    for (i=2;i<=n;i++){
        best[i]=best[i-1];
        int l=1,r=i-1;
        if (a[1].r>a[i].l) {
                best[i]=a[i].r-a[i].l;
                continue;
        }
        int sol;
        while (l<=r){
            int m=(l+r)/2;
            if (a[m].r<=a[i].l)
                sol=m,l=m+1;
            else r=m-1;
        }
        best[i]=max(best[i],best[sol]+a[i].r-a[i].l);
    }
    cout<<best[n];
    return 0;
}