Cod sursa(job #1692204)

Utilizator raddudjPogonariu Radu raddudj Data 20 aprilie 2016 14:20:32
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <cstdio>
#include <algorithm>

using namespace std;

const int NMAX = 100000;

struct Metal {
    int x,y;
    Metal() {}
    Metal(int a,int b) {
        x=a,y=b;
    }
    bool operator< (const Metal &other) const {
        return y < other.y;
    }
};

Metal v[NMAX + 5];
int d[NMAX + 5];

int main() {
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
    int n,maxim = -1;
    scanf("%d",&n);
    for(int i=1; i<=n; i++) {
        int x,y;
        scanf("%d%d",&x,&y);
        v[i]=Metal(x,y);
    }
    sort(v+1,v+n+1);
    for(int i=1; i<=n; i++) {
        if ( v[i].x>v[1].y ) {
            int st=1,dr=i;
            while(st<=dr) {
                int med=(st + dr)/2;
                if(v[med].y <= v[i].x)
                    st=med+1;
                else
                    dr=med-1;
            }
            int med=(st + dr)/2;
            if(v[med].y>v[i].x)
                med--;
            d[i]=max(d[med]+v[i].y-v[i].x, maxim);
        } else
            d[i]=max( v[i].y-v[i].x, maxim );
        if(d[i]>maxim)
            maxim=d[i];
    }
    printf("%d\n",maxim);
}