Cod sursa(job #1699454)

Utilizator cristina_borzaCristina Borza cristina_borza Data 7 mai 2016 12:47:00
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <algorithm>
#include <fstream>

#define NMAX 100005

using namespace std;

ifstream f("heavymetal.in");
ofstream g("heavymetal.out");

struct qq {
    long long st , en;
} v[NMAX];

long long dp[NMAX];
long long n;

bool comp(qq a , qq b) {
    return a.en < b.en || (a.en == b.en && a.st < b.st);
}

long long caut_bin(long long val);

int main() {
    f >> n;
    for(int i = 1 ; i <= n ; ++i) {
        f >> v[i].st >> v[i].en;
    }

    sort(v + 1 , v + n + 1 , comp);
    for(int i = 1 ; i <= n ; ++i) {
        long long p = caut_bin(v[i].st);
        dp[i] = dp[p] + v[i].en - v[i].st;
        dp[i] = max(dp[i] , dp[i - 1]);
    }

    g << dp[n];
    return 0;
}

long long caut_bin(long long val) {
    long long i , p = 0;
    for(i = 1 ; i <= n ; i <<= 1);
    while(i) {
        if(i + p <= n && v[i + p].en <= val) {
            p += i;
        }
        i >>= 1;
    }

    return p;
}