Pagini recente » Cod sursa (job #1921757) | Cod sursa (job #2365677) | Cod sursa (job #1748781) | Cod sursa (job #597441) | Cod sursa (job #344621)
Cod sursa(job #344621)
#include <cstdio>
#include <fstream.h>
#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;
ifstream fin("lupu.in");
fin>>n>>X>>L;
for(long i=1;i<=n;i++)
{
fin>>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];
}
fin.close();
}
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()
{
ofstream fout("lupu.out");
fout<<S;
fout.close();
}
int main()
{
cit();
if(!L)
S=s;
else
sol();
afis();
return 0;
}