Pagini recente » Cod sursa (job #513526) | Cod sursa (job #1858195) | Cod sursa (job #278947) | Cod sursa (job #2640365) | Cod sursa (job #438026)
Cod sursa(job #438026)
#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("gutui.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("gutui.out","w");
fprintf(fout,"%lld\n",total_lana);
fclose(fout);
return 0;
}