Cod sursa(job #1517096)

Utilizator raulmuresanRaul Muresan raulmuresan Data 3 noiembrie 2015 20:53:35
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
/*
Cautam binar cel mai din dreapta interval care capatul din dreapta mai mic sau egal decat capatul din stanga al intervalului curent
*/
#include <fstream>
#include <cstdio>
#include <algorithm>
#define NMax 100002
using namespace std;

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

int A[NMax],B[NMax],Best[NMax],i;
int TMax;
struct coada
{
    int x,y;
}V[NMax];


bool cmp(coada i,coada j)
{
    return i.y<j.y;
}

int main()
{
    int n,x,y,sol;
    fin>>n;
    for( i=1;i<=n;i++)
    {
        fin>>V[i].x>>V[i].y;
    }

    sort(V+1,V+n+1,cmp);

    Best[1]=V[1].y-V[1].x;
    sol=Best[1];

    for( i=2;i<=n;i++)
    {
        Best[i]=Best[i-1];
        int s=1;
        int d=i-1;
        int j=0;
        while(s<=d)
        {
            int mij=(s+d)/2;
            if(V[mij].y<=V[i].x)
            {
                j=mij;
                s=mij+1;
            }
            else
                d=mij-1;
        }
            Best[i]=max(Best[i],Best[j]+V[i].y-V[i].x);

    }

    for(i=1;i<=n;i++)
    {
        sol=max(sol,Best[i]);
    }
    fout<<sol<<"\n";

}