Cod sursa(job #1223832)

Utilizator andreiblaj17Andrei Blaj andreiblaj17 Data 28 august 2014 22:34:50
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 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;
interval A[nmax];

int i;
int DP[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 x, int hi) {
    
    int lo = 1;
    
    while (lo <= hi) {
        
        int mid = (hi + lo) >> 1;
        
        if (A[mid].y <= x)
            lo = mid + 1;
        else
            hi = mid - 1;
        
    }
    
    return DP[hi];
    
}

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