Cod sursa(job #142709)

Utilizator vanila_CPPIonescu Victor Cristian vanila_CPP Data 25 februarie 2008 00:17:54
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <cstdio>
#include <algorithm>
#define MAX_N 100000
#define FIN "heavymetal.in"
#define FOUT "heavymetal.out"
using namespace std;
struct normalizat{
        int vl,ind;
} v[2*MAX_N+1];
int vcpy[2*MAX_N+1];
struct list{
        int inf;
        list* urm;
} *rel[MAX_N*2+1];
int n,normal[2*MAX_N+1],best[2*MAX_N+1];


bool fcmp1(const normalizat& x, const normalizat& y){
        return (x.vl<y.vl);
}


bool fcmp2(const normalizat& x, const normalizat& y){
        return (x.ind<y.ind);
}

void iofile(void){
        freopen(FIN,"rt",stdin);
        freopen(FOUT,"wt",stdout);
        
        scanf("%d",&n); //citesc
        for (int i=1;i<=n;i++){
                scanf("%d%d",&v[2*i-1].vl,&v[2*i].vl);
                vcpy[2*i-1]=v[2*i-1].vl;//retin
                vcpy[2*i]=v[2*i].vl;   //o copie
                v[2*i].ind=2*i;
                v[2*i-1].ind=2*i-1;
        }

        sort(v+1,v+2*n+1,fcmp1); //normalizam :)
        int nrnrm=0;
        for (int i=1;i<=2*n;i++){
                if (v[i].vl==v[i-1].vl){
                        normal[i]=nrnrm;} else {normal[i]=++nrnrm;}
        }


        for (int i=1;i<=2*n;i++){
                v[i].vl=normal[i];
        }
        for (int i=1;i<=2*n;i++){
                rel[i]=0;
        }
        list *q;
        for (int i=1;i<=2*n;i++){
                if ((v[i].ind & 1)==0){
                        q=new list;
                        q->inf=v[i].ind/2;
                        q->urm=rel[v[i].vl];
                        rel[v[i].vl]=q;
                }
        }


        sort(v+1,v+2*n+1,fcmp2);
        best[0]=0;//here starts dinamica xD
        for (int i=1;i<=nrnrm;i++){
                best[i]=best[i-1];
                q=rel[i];
                while (q){
                        best[i]=max(best[i],best[v[2*q->inf-1].vl]+
                                vcpy[2*q->inf]-vcpy[2*q->inf-1]);
                        q=q->urm;
                }
        }
        printf("%d\n",best[nrnrm]);
        fclose(stdout);
        return ;
}


int main(void){
        iofile();
        return 0;
}