Cod sursa(job #2536141)

Utilizator verde.cristian2005Verde Flaviu-Cristian verde.cristian2005 Data 1 februarie 2020 16:03:47
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <fstream>
#include <algorithm>
#define a first
#define b second
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
pair <int,int> v[100001];
int best[100001];
int n;
int cautbin(int val) {
    int r=0,pas=1<<16;
    while(pas) {
        if(r+pas<=n&&v[r+pas].b<=val)
            r+=pas;
        pas/=2;
    }
    return r;
}
int main() {
    int i,x;
    in>>n;
    for(i=1; i<=n; i++)
        in>>v[i].b>>v[i].a;
    sort(v+1,v+n+1);
    for(i=1; i<=n; i++)
        v[i].a^=v[i].b^=v[i].a^=v[i].b;
    for(i=1; i<=n; i++) {
        x=cautbin(v[i].a);
        best[i]=max(best[i-1],best[x]+v[i].b-v[i].a);
    }
    out<<best[n];
    return 0;
}