Cod sursa(job #1288370)

Utilizator radu_cebotariRadu Cebotari radu_cebotari Data 8 decembrie 2014 19:32:14
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
const int NMAX  = 100000;

struct concert{
    int a,b;
};
concert v[NMAX + 1];
int sol[NMAX + 1],n;

void read()
{

    in>>n;
    for(int i = 1 ; i <= n ; i++)
        in>>v[i].a>>v[i].b;
    in.close();
}

bool cmp(concert x,concert y){
    return x.b < y.b;
}

int bin_search(int left,int right,int val)
{

    int mid,s = -1;
    while(left <= right){
        mid = (left+right)>>1;
        if(v[mid].b <= val)
            left = mid + 1,s = mid;
        else
            right = mid - 1;
    }
    return s;
}

void solve()
{

    sort(v+1,v+n+1,cmp);
    sol[1] = v[1].b-v[1].a;
    for(int i = 2 ; i <= n ; i++){
        sol[i] = sol[i-1];
        int key = bin_search(1,i-1,v[i].a);
        if(key != -1)
            sol[i] = max(sol[i],sol[key] + (v[i].b-v[i].a));
        else
            sol[i] = max(sol[i],v[i].b-v[i].a);
    }
    out<<sol[n];
    out.close();
}

int main()
{

    read();
    solve();
    return 0;
}