Pagini recente » Cod sursa (job #2645611) | Cod sursa (job #260734) | Cod sursa (job #2884275) | Cod sursa (job #1674861) | Cod sursa (job #2498425)
#include<fstream>
#include<algorithm>
#define nmax 100005
using namespace std;
ifstream f ("lupu.in");
ofstream g ("lupu.out");
unsigned long long heap[nmax],i,j,n,m,x,l,distanta,lana,cnt;
unsigned long long sol;
void percolate(unsigned long long k)
{
unsigned long long tata=k/2;
while(k>1 && heap[tata]<heap[k])
{
swap(heap[tata],heap[k]);
k=tata;
tata=k/2;
}
}
void sift (unsigned long long k)
{
unsigned long long fiu=1;
while(fiu)
{
fiu=0;
if(2*k<=n)
fiu=2*k;
if(2*k+1<=n && heap[2*k+1]>heap[fiu])
fiu=2*k+1;
if(heap[k]>heap[fiu])
fiu=0;
else
{
swap(heap[k],heap[fiu]);
k=fiu;
}
}
}
struct ele
{
unsigned long long lana,distanta;
}oaie[nmax];
bool cmp(ele a,ele b)
{
return a.distanta>b.distanta;
}
int main()
{
f>>n>>x>>l;
for(i=1;i<=n;i++)
{
f>>distanta>>lana;
if(distanta<=x)
{
oaie[++cnt].distanta=(x-distanta)/l+1;
oaie[cnt].lana=lana;
}
}
sort(oaie+1,oaie+cnt+1,cmp);
unsigned long long tmax=oaie[1].distanta,pos=1,ok=0;
n=0;
while(tmax!=0 && pos<=cnt)
{
ok=0;
while(tmax==oaie[pos].distanta && pos<=cnt)
{
n++;
ok=1;
heap[n]=oaie[pos].lana;
percolate(n);
pos++;
}
if(n!=0)
{
sol+=heap[1];
heap[1]=heap[n];
n--;
if(n>1)
{
sift(1);
}
}
tmax--;
}
g<<sol;
}