Cod sursa(job #1078909)

Utilizator CiurezAndreiCiurez Marius-Andrei CiurezAndrei Data 12 ianuarie 2014 11:48:54
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
struct metal{
    int a,b;
}v[100001];
int cmp(metal x,metal y){
    if (x.b<y.b) return 1;
    if (x.b==y.b&&x.a<y.a) return 1;
    return 0;
}
long long b[100001];
int i,j,n,p,u,mij,sol,act;
int main()
{
    f>>n;
    for(i=1;i<=n;i++){
        f>>v[i].a>>v[i].b;
    }
    sort(v+1,v+n+1,cmp);
    b[1]=v[1].b-v[1].a;
    for(i=2;i<=n;i++){
        p=1;
        u=i-1;
        sol=0;
        while(p<=u){
            mij=(p+u)/2;
            if(v[i].a>=v[mij].b){
                sol=mij;
                p=mij+1;
            }
            else
                u=mij-1;
        }
        b[i]=b[i-1];
        act=v[i].b-v[i].a;
        if(b[i]<b[sol]+act)
            b[i]=b[sol]+act;

    }
    g<<b[n];
    return 0;
}