Cod sursa(job #437425)

Utilizator mockeBarca Cristian Mihai mocke Data 9 aprilie 2010 18:18:25
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include <stdio.h>

#define NMAX 100001

FILE *fin,*fout;

struct sheap
{long v,ind;
}h[NMAX+1];

int l_heap;
int T,N,X,L;
struct oaie
{long dist,lana,tmin;
}oi[NMAX+1];

void Combina(long vf,long nn)
{long baza;
 oaie val=oi[vf];
 for (baza=2*vf;baza<=nn;baza*=2)
     {if (baza<nn&&oi[baza].tmin<oi[baza+1].tmin) ++baza;
      if (val.tmin<oi[baza].tmin)
         {oi[vf]=oi[baza];vf=baza;}
      else break;
     }
 oi[vf]=val;
}
void Heap()
{long i;
 for (i=N/2;i>=1;--i) Combina(i,N);
}
void Heapsort()
{long i;
 oaie aux;
 Heap();
 for (i=N;i>1;--i)
     {aux=oi[i];oi[i]=oi[1];oi[1]=aux;
      Combina(1,i-1);
     }
}

void insert_heap(long timp,long ap)
{sheap val;
 int vf,baza;
 ++l_heap;
 h[l_heap].ind=timp;h[l_heap].v=ap;
 for (vf=l_heap,val=h[l_heap],baza=l_heap/2;baza>0;baza/=2)
     {if (val.v<h[baza].v) {h[vf]=h[baza];vf=baza;}
      else break;
     }
 h[vf]=val;
}
void pop_heap(long &timp)
{sheap val;
 int vf,baza;
 timp=h[1].ind;
 h[1]=h[l_heap];--l_heap;
 for (vf=1,val=h[1],baza=2;baza<=l_heap;baza*=2)
     {if (baza<l_heap&&h[baza].v>h[baza+1].v) ++baza;
      if (val.v>h[baza].v) {h[vf]=h[baza];vf=baza;}
      else break;
     } 
 h[vf]=val;
}
 
int main()
{long last,i,j,k,timp;
 long long total_lana=0;
 fin=fopen("lupu.in","r");
 fscanf(fin,"%ld %ld %ld",&N,&X,&L);
 for (i=1;i<=N;++i)
     {fscanf(fin,"%ld %ld",&oi[i].dist,&oi[i].lana);
      if (X<oi[i].dist) oi[i].tmin=0;
      else oi[i].tmin=(X-oi[i].dist)/L+1; 
     }
 fclose(fin);
 Heapsort(); 
 for (i=1;i<=N&&!oi[i].tmin;++i);
 last=1;
 for (;i<=N;i=j)
     {for (j=i;j<=N&&oi[j].tmin==oi[i].tmin;++j);
      for (;last<=oi[i].tmin;++last) insert_heap(last,0);
      for (k=i;k<j;++k)
          if (h[1].v<oi[k].lana)
             {pop_heap(timp);
              insert_heap(timp,oi[k].lana);
             } 
     }
 for (i=1;i<=l_heap;++i) total_lana+=h[i].v;
 fout=fopen("lupu.out","w");
 fprintf(fout,"%lld\n",total_lana);
 fclose(fout); 
 return 0;
}