Pagini recente » Cod sursa (job #1896411) | Cod sursa (job #2887387) | Cod sursa (job #255693) | Cod sursa (job #654994) | Cod sursa (job #157107)
Cod sursa(job #157107)
#include<stdio.h>
FILE*fin=fopen("heavymetal.in","r");
FILE*fout=fopen("heavymetal.out","w");
#define maxn 100001
#define inf 1000000000
#define fmax(a,b)((a)>(b)?(a):(b))
int best[maxn],a[maxn],b[maxn],v[maxn],n;
void rec(int nod,int dim)
{
int nd=nod,max=b[nod],st,dr;st=nod<<1;dr=st+1;
if(max<b[st]&&st<=dim){max=b[st];nd=st;}
if(max<b[dr]&&dr<=dim){max=b[dr];nd=dr;}
if(nd!=nod)
{
b[nd]^=b[nod]^=b[nd]^=b[nod];
a[nd]^=a[nod]^=a[nd]^=a[nod];
rec(nd,dim);
}
}
void ord()
{
int i,dim;
for(i=n/2;i>=1;i--)
rec(i,n);
dim=n;
while(dim>1)
{
a[1]^=a[dim]^=a[1]^=a[dim];
b[1]^=b[dim]^=b[1]^=b[dim];
dim--;
rec(1,dim);
}
}
int main()
{
int i,st,dr,dv,prev,v1,v2,mij;
fscanf(fin,"%d",&n);
for(i=1;i<=n;i++)
fscanf(fin,"%d%d",&a[i],&b[i]);
fclose(fin);
ord();
v[0]=0;best[0]=0;
dv=0;
for(i=1;i<=n;i++)
{
if(b[i]==v[dv]) prev=dv-1;
else{prev=dv;dv++;best[dv]=-inf;}
v1=best[prev];
st=0;dr=prev;
while(st<dr-1)
{
mij=(st+dr)/2;
if(v[mij]<=a[i]) st=mij;
else dr=mij-1;
}
if(v[dr]<=a[i]) prev=dr;
else prev=st;
v2=b[i]-a[i]+best[prev];
v1=fmax(v1,v2);
best[dv]=fmax(best[dv],v1);
v[dv]=b[i];
}
fprintf(fout,"%d",best[dv]);
fclose(fout);
return 0;
}