Cod sursa(job #474895)

Utilizator freak93Adrian Budau freak93 Data 5 august 2010 15:05:42
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include<fstream>
#include<algorithm>

using namespace std;

const char iname[]="heavymetal.in";
const char oname[]="heavymetal.out";
const int maxn=100005;

ifstream f(iname);
ofstream g(oname);

struct x
{
    int x,y;
}a[maxn];

bool operator<(const x& a,const x& b)
{
    return a.y<b.y;
}

int n,i,step,j,v[maxn],maxt;

int main()
{
    f>>n;
    for(i=1;i<=n;++i)
        f>>a[i].x>>a[i].y;
    sort(a+1,a+n+1);
    for(i=1;i<=n;++i)
    {
        for(step=1;step<i;step<<=1);
        for(j=0;step;step>>=1)
            if(j+step<i&&a[j+step].y<=a[i].x)
                j+=step;
        v[i]=max(v[i-1],a[i].y-a[i].x+v[j]);
    }
    g<<v[n]<<"\n";
}