Pagini recente » Arhiva de probleme | Cod sursa (job #2573645) | Cod sursa (job #1031366) | Cod sursa (job #580068) | Cod sursa (job #249849)
Cod sursa(job #249849)
#include<fstream.h>
int norm[100010],best[100010],i,j,p,k,n;
struct sir {int x,y;} v[100010];
int poz(int i,int j)
{ int di,dj,aux;
sir aux2;
di=0; dj=1;
while(i<j)
{ if(v[i].y>v[j].y) { aux2=v[i]; v[i]=v[j]; v[j]=aux2;
aux=di; di=dj; dj=aux;
}
i+=di; j-=dj;
}
return i;
}
void quick(int s, int d)
{ if(s<d)
{ int p=poz(s,d);
quick(s,p-1);
quick(p+1,d);
}
}
int cautare(int val)
{ int s,d,m;
s=1; d=n; m=(s+d)>>1;
while(s<d)
{
if(v[m].y>val) d=m-1;
else if(v[m].y<val) s=m+1;
else break;
m=(s+d)>>1;
}
return m;
}
int main()
{
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
f>>n;
for(i=1;i<=n;i++) f>>v[i].x>>v[i].y;
quick(1,n);
k=1; norm[1]=1;
for(i=2;i<=n;i++)
if(v[i].y==v[i-1].y) norm[i]=norm[i-1];
else {k++; norm[i]=k;}
best[1]=v[1].y-v[1].x;
for(i=2;i<=n;i++)
{ best[i]=best[i-1];
j=i;
while(norm[j]==norm[i])
{ p=cautare(v[j].x);
if(best[i]<best[p]+v[j].y-v[j].x)
best[i]=best[p]+v[j].y-v[j].x;
j--;
}
}
g<<best[n];
f.close();
g.close();
return 0;
}