Cod sursa(job #157107)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 12 martie 2008 21:08:53
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#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;
}