Cod sursa(job #1217895)

Utilizator somuBanil Ardej somu Data 8 august 2014 17:03:37
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

#define nmax 100005
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");

struct interval {
    int x,y;
};

int n,i,x,M;
int L[nmax];
interval A[nmax];

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

int bs(int hi) {
    
    int lo = 1, maxim = 0, mid;

    while (hi>=lo) {
        
        mid = (hi + lo) >> 1;
        
        if (A[i].x < A[mid].y)
            hi = mid - 1;
        else
            maxim = max(maxim, L[mid]),
            lo = mid + 1;
        
    }
    
    return maxim;
}

int main() {
    
    in >> n;
    
    for (i=1; i<=n; i++)
        in >> A[i].x >> A[i].y;
    
    sort(A+1, A+n+1, cmp);
    
    L[1] = A[1].y - A[1].x;
    
    M = L[1];
    
    for (i=2; i<=n; i++)
        x = bs(i-1),
        L[i] = A[i].y - A[i].x,
        L[i] = max(L[i], L[i]+x),
        M = max(M, L[i]);
    
    out << M << "\n";
    
    return 0;
}