Cod sursa(job #2378748)

Utilizator ilie0712Botosan Ilie ilie0712 Data 12 martie 2019 16:35:02
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

const int N=100002;
const int L=29;

int n,a,b,d[N];


struct obiect
{
    int ora_inc;
    int ora_sf;
} v[N];


int caut1(int x)
{
    int pas=1<<L;
    int r=0;
    while(pas!=0)
    {
        if(r+pas<=n && v[r+pas].ora_sf<=x)
            r+=pas;
        pas/=2;
    }
    return r;
}

bool cmp(obiect x, obiect y)
{
    return x.ora_sf < y.ora_sf;
}

void citire()
{
    in>>n;
    for(int i=1; i<=n; ++i) in>>v[i].ora_inc>>v[i].ora_sf;
    sort(v+1,v+n+1,cmp);
}


int main()
{
    citire();
    for(int i=1; i<=n; ++i)
        {
            int a=v[i].ora_sf-v[i].ora_inc+d[caut1(v[i].ora_inc)];
            d[i]=max(d[i-1],a);
        }
        out<<d[n];
    return 0;
}