Cod sursa(job #1061255)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 19 decembrie 2013 15:17:40
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <fstream>
#include <algorithm>

using namespace std;

int v[200005],best[100005];
int n,i,st,dr,val,mid,k,tmax,j;

struct data{
            int a;
            int b;
            int vec;
        }s[100005];

bool cmp(const data &s1, const data &s2){
    if(s1.b<s2.b)
        return 1;
    else
        return (s1.a<s1.a);
}

int main(){

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

    f>>n;
    for(i=1;i<=n;i++){
        k++;
        f>>s[i].a;
        v[k]=s[i].a;
        k++;
        f>>s[i].b;
        v[k]=s[i].b;
        s[i].vec=s[i].b-s[i].a;
    }
    sort(v+1,v+k+1);
    for(i=1;i<=n;i++){
        val=s[i].a;
        st=1;dr=k;
        while(st<=dr){
            mid=(st+dr)/2;
            if(v[mid]<val)
                st=mid+1;
            else
                dr=mid-1;
        }
        s[i].a=st;
        val=s[i].b;
        st=1;dr=k;
        while(st<=dr){
            mid=(st+dr)/2;
            if(v[mid]<val)
                st=mid+1;
            else
                dr=mid-1;
        }
        s[i].b=st;
        if(s[i].b>tmax)
            tmax=s[i].b;
    }
    sort(s+1,s+n+1,cmp);

    for(i=1;i<=tmax;i++){
        best[i]=best[i-1];
        st=1;dr=n;
        while(st<=dr){
            mid=(st+dr)/2;
            if(s[mid].b<i)
                st=mid+1;
            else
                dr=mid-1;
        }
        for(j=st;s[j].b==i;j++){
            if(best[i]<best[s[j].a]+(s[j].vec))
                best[i]=best[s[j].a]+(s[j].vec);
        }
    }
    g<<best[tmax]<<"\n";
    /*for(i=1;i<=n;i++)
        g<<s[i].a<<" "<<s[i].b<<"\n";*/
    f.close();g.close();
    return 0;
}