Cod sursa(job #2002779)

Utilizator AronZekAron Jinga AronZek Data 20 iulie 2017 18:58:25
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <algorithm>
#include <fstream>
#define PII pair<int, int>
#define x first
#define y second
#define N 10004

using namespace std;

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

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

int binarys(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()
{
    ifstream fin("heavymetal.in");
    ofstream fout("heavymetal.out");
    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=binarys(i-1, a[i].x);
        b[i]=max(b[i-1], b[x]+a[i].y-a[i].x);
    }
    fout<<b[n];