Cod sursa(job #1083671)

Utilizator alexandru213Bracau Alexandru alexandru213 Data 16 ianuarie 2014 11:12:25
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
struct ore {
    int oi,of;
    }v[100001];
int n,i;
long long a[100001];
int cmp(ore x,ore y){
    if(x.of<y.of)
        return 1;
    if(x.of==y.of&&x.oi<y.oi)
        return 1;
    return 0;
}
int caut(int u,int x){
int p=1,mij,sol=0;
while(p<=u){
    mij=(p+u)/2;
    if(x>=v[mij].of){
        sol=mij;
        p=mij+1;}
    else
        u=mij-1;
}
return sol;


}
int main()
{
    in>>n;
    for(i=1;i<=n;i++){
        in>>v[i].oi>>v[i].of;}
    sort(v+1,v+n+1,cmp);
    a[1]=v[1].of-v[1].oi;
    for(i=2;i<=n;i++){
        a[i]=a[i-1];
       int p=caut(i-1,v[i].oi);
        if(a[i]<a[p]+v[i].of-v[i].oi)
            a[i]=a[p]+v[i].of-v[i].oi;
        }
    out<<a[n];
    return 0;
}