Pagini recente » Cod sursa (job #2883555) | Cod sursa (job #149525) | Cod sursa (job #462787) | Cod sursa (job #408561) | Cod sursa (job #344620)
Cod sursa(job #344620)
#include <cstdio>
#include <vector>
#define MaxN 100009
#define t(x) ((x)/2)
#define fs(x) ((x)*2)
#define fd(x) ((x)*2+1)
using namespace std;
vector <long long> T[MaxN];
long long D[MaxN],A[MaxN],X,L,n,heap[MaxN],N,S,T_max,s;
void cit()
{
long 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 && L)
{
x=(X-D[i])/L+1;
T[x].push_back(i);
if(x>T_max)
T_max=x;
}
if(D[i]<=X)
s+=A[i];
}
}
void swap(long long x,long long y)
{
long long aux=heap[x]; heap[x]=heap[y]; heap[y]=aux;
}
void upheap(long long nod)
{
while(nod>1 && A[heap[nod]]>A[heap[t(nod)]])
swap(nod,t(nod)), nod=t(nod);
}
void add(long long p)
{
N++;
heap[N]=p;
upheap(N);
}
void downheap(long long nod)
{
while((fs(nod)<=N && A[heap[nod]]<A[heap[fs(nod)]]) || (fd(nod)<=N && A[heap[nod]]<A[heap[fd(nod)]]))
if(fd(nod)<=N)
{
if(A[heap[fs(nod)]]>A[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 long nod)
{
heap[nod]=heap[N];
heap[N]=0; N--;
downheap(nod);
}
void sol()
{
long 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+=A[heap[1]];
if(N>0)
erase(1);
}
}
void afis()
{
freopen("lupu.out","w",stdout);
printf("%ld",S);
}
int main()
{
cit();
if(!L)
S=s;
else
sol();
afis();
return 0;
}