Cod sursa(job #1740784)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 12 august 2016 12:25:52
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <cstdio>
#include <algorithm>
using namespace std;
int d[100005];
struct HEAVY{
    int x, y;
}v[100005];
int bs(int st, int dr, int capat){
    int med, last = -1;
    while (st <= dr){
        med = (st + dr) / 2;
        if (v[med].y <= capat){
            last = med;
            st = med + 1;
        }
        else
            dr = med - 1;
    }
    return last;
}
bool cmp(HEAVY a, HEAVY b){
    return a.y < b.y;
}
int main(){
    freopen("heavymetal.in", "r", stdin);
    freopen("heavymetal.out", "w", stdout);
    int n, x, y, i, j, max1 = 0;
    scanf("%d", &n);
    for (i = 1; i <= n; i ++){
        scanf("%d%d", &x, &y);
        v[i].x = x;
        v[i].y = y;
    }
    sort(v + 1, v + n + 1, cmp);
    for (i = 1; i <= n; i ++){
        j = bs(1, n, v[i].x);
        d[i] = max(d[i - 1], d[j] + v[i].y - v[i].x);
        if (max1 < d[i])
            max1 = d[i];
    }
    printf("%d\n", max1);
    return 0;
}