Cod sursa(job #1066415)

Utilizator andreiiiiPopa Andrei andreiiii Data 24 decembrie 2013 18:20:46
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <algorithm>
#include <fstream>
#define PII pair<int, int>
#define x first
#define y second

using namespace std;

const int N=10004;

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

PII a[N];
int b[N];

bool comp(PII a, PII b)
{
    return a.y<b.y;
}

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

int main()
{
    int n, i, x;
    fin>>n;
    for(i=1;i<=n;i++) fin>>a[i].x>>a[i].y;
    sort(a+1, a+n+1, comp);
    for(i=1;i<=n;i++)
    {
        x=bs(i, a[i].x);
        b[i]=max(b[i-1], b[x]+a[i].y-a[i].x);
    }
    fout<<b[n];
}