Pagini recente » Cod sursa (job #1123142) | Cod sursa (job #982787) | Cod sursa (job #2373235) | Cod sursa (job #2856009) | Cod sursa (job #342976)
Cod sursa(job #342976)
#include <cstdio>
#include <vector>
#define MaxN 1009
#define t(x) ((x)/2)
#define fs(x) ((x)*2)
#define fd(x) ((x)*2+1)
using namespace std;
vector <long> T[MaxN];
long D[MaxN],A[MaxN],X,L,n,heap[MaxN],N,S,T_max;
void cit()
{
long x;
freopen("lupu.in","r",stdin);
scanf("%ld%ld%ld",&n,&X,&L);
for(long i=1;i<=n;i++)
{
scanf("%ld%ld",&D[i],&A[i]);
if(D[i]<=X)
{
x=(X-D[i])/L+1;
T[x].push_back(i);
if(x>T_max)
T_max=x;
}
}
}
void swap(long x,long y)
{
long aux=heap[x]; heap[x]=heap[y]; heap[y]=aux;
}
void upheap(long nod)
{
while(nod>1 && heap[nod]>heap[t(nod)])
swap(nod,t(nod)), nod=t(nod);
}
void add(long p)
{
N++;
heap[N]=A[p];
upheap(N);
}
void downheap(long 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(long nod)
{
heap[nod]=heap[N];
heap[N]=0; N--;
if(N>1)
downheap(nod);
}
void sol()
{
long i,j,max,p;
for(i=T_max;i>=1;i--)
{
max=0;
for(j=0;j<T[i].size();j++)
{
p=T[i][j];
add(p);
}
S+=heap[1];
if(N>0)
erase(1);
}
}
void afis()
{
freopen("lupu.out","w",stdout);
printf("%ld",S);
}
int main()
{
cit();
sol();
afis();
return 0;
}