Pagini recente » Cod sursa (job #1035367) | Cod sursa (job #2048737) | Cod sursa (job #1151379) | Cod sursa (job #2046103) | Cod sursa (job #342556)
Cod sursa(job #342556)
#include <fstream.h>
#define MaxN 100009
#define t(x) ((x)/2)
#define fs(x) ((x)*2)
#define fd(x) ((x)*2+1)
long d[MaxN],l[MaxN],T[MaxN],pos[MaxN],heap[MaxN],T_max,X,L,n,s,k,N;
void cit()
{
int i;
ifstream fin("lupu.in");
fin>>n>>X>>L;
for(i=1;i<=n;i++)
fin>>d[i]>>l[i];
fin.close();
}
void sch(int i,int j)
{
long aux=d[i]; d[i]=d[j]; d[j]=aux;
aux=l[i]; l[i]=l[j]; l[j]=aux;
}
void poz(int li,int ls)
{
long i=0,j=-1,c;
while(li<ls)
{
if(d[li]>d[ls])
{
sch(li,ls);
c=i; i=-j; j=-c;
}
li+=i; ls+=j;
}
k=li;
}
void quick(int li,int ls)
{
if(li<ls)
{
poz(li,ls);
quick(li,k-1);
quick(k+1,ls);
}
}
void timp()
{
long t=0,i=n,nr=0;
while(d[i]>X && i>=1)
i--;
while(i>=1)
{
while(d[i]+t>X && i>=1)
T[i]=nr, pos[nr]=i, i--;
nr++;
t+=L;
}
T_max=nr-1;
}
void swap(int x,int y)
{
int aux=heap[x];
heap[x]=heap[y];
heap[y]=aux;
}
void upheap(int nod)
{
while(nod>1 && heap[t(nod)]<heap[nod])
{
swap(t(nod),nod);
nod=t(nod);
}
}
void insert(int val)
{
N++;
heap[N]=val;
upheap(N);
}
void downheap(int nod)
{
while(fs(nod)<=N && heap[nod]<heap[fs(nod)] || fd(nod)<=N && heap[nod]<heap[fd(nod)])
if(fd(nod)<=N)
{
if(heap[fs(nod)]>heap[fd(nod)])
{
swap(nod,fs(nod));
nod=fs(nod);
}
else
{
swap(nod,fd(nod));
nod=fd(nod);
}
}
else
{
swap(nod,fs(nod));
nod=fs(nod);
}
}
void erase(int nod)
{
swap(nod,N);
N--;
downheap(1);
}
void sol()
{
int i,nr=0;
for(i=T_max;i>=1;i--)
{
k=pos[i];
while(T[k]==i && k<=n)
insert(l[k]), k++;
s+=heap[1];
if(N>=1)
erase(1);
}
}
void afis()
{
ofstream fout("lupu.out");
fout<<s;
fout.close();
}
int main()
{
cit();
quick(1,n);
timp();
sol();
afis();
return 0;
}