Cod sursa(job #1219647)

Utilizator hasmasandragosHasmasan Dragos hasmasandragos Data 14 august 2014 18:52:34
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <fstream>
#include <algorithm>
using namespace std;

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

const int nmax=100005;
int n,i,j,v[nmax],p;
struct spectacol {int bg,end;};
spectacol a[nmax];

bool cmp (spectacol A,spectacol B)
{
    if (A.end!=B.end)
     return A.end<B.end;
    if (A.bg!=B.bg)
     return A.bg>B.bg;
}

int binsearch (int val)
{
    int step,rez=0;
    for (step=1;step<=n;step<<=1);
    for (rez=0;step;step>>=1)
     if (rez+step<=n && a[rez+step].end<=val)
      rez+=step;
    return rez;
}

int main()
{
    f>>n;
    for (i=1;i<=n;i++)
     f>>a[i].bg>>a[i].end;
    sort(a+1,a+n+1,cmp);
    v[1]=a[1].end-a[1].bg;
    for (i=2;i<=n;i++)
    {
        p=binsearch(a[i].bg);
        v[i]=max(v[i-1],a[i].end-a[i].bg+v[p]);
    }
    g<<v[n];
    return 0;
}