Pagini recente » Cod sursa (job #1251187) | Cod sursa (job #200337) | Cod sursa (job #870546) | Cod sursa (job #2335239) | Cod sursa (job #142709)
Cod sursa(job #142709)
#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;
}