Cod sursa(job #1123697)

Utilizator cristibogdanPatrascu Cristian cristibogdan Data 26 februarie 2014 09:42:26
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
struct punct {
        int x;
        int y;}v[100001];
    int cmp( punct a , punct b){
            if(a.y<b.y)
                    return 1;
                if(a.y==b.y&&a.x<b.x)
                        return 1;
                    return 0;}
int i,n,st,dr,mij,c[100001];
int main()
{f>>n;
    for(i=1;i<=n;i++){
            f>>v[i].x>>v[i].y;}
    sort(v+1,v+n+1,cmp);

           c[1]=v[1].y-v[1].x;
                for(i=2;i<=n;i++){
                        st=1;dr=n;
                            while(st<=dr){
                                    mij=(st+dr)/2;
                                        if(v[i].x>=v[mij].y)
                                                st=mij+1;
                                            else
                                                    dr=mij-1;}
                            if(c[i-1]<c[dr]+v[i].y-v[i].x)
                                    c[i]=c[dr]+v[i].y-v[i].x;
                            else
                                c[i]=c[i-1];}
            g<<c[n];
    return 0;
}