Cod sursa(job #2046866)

Utilizator KemyKoTeo Virghi KemyKo Data 24 octombrie 2017 10:24:01
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#define NMAX 100001

using namespace std;

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

int n,fv[NMAX],rez[NMAX],mx,rezultat;
struct metal
{
    int st,dr;
}v[NMAX];

void citire()
{
    int i;
    f>>n;
    for (i=1;i<=n;i++)
        f>>v[i].st>>v[i].dr;
}

int comp(metal a,metal b)
{
    if (a.dr == b.dr)
        return (a.st < b.st);
    return (a.dr < b.dr);
}

int c_binara(int x)
{
    int p=1,u=n,m=(p+u)/2;
    while (p<=u){
        m=(p+u)/2;
        if (v[m].dr<=x)p=m+1;
        else u=m-1;
    }
    return u;
}

void afis()
{
    int i,k,j;
    for (i=1;i<=n;i++){
        j=c_binara(v[i].st);
        rez[i]=max(rez[i-1], rez[j]+v[i].dr-v[i].st);
        rezultat=max(rezultat, rez[i]);
    }
    g<<rezultat;
}

int main()
{
    citire();
    sort(v+1,v+1+n,comp);
    afis();
    return 0;
}