Pagini recente » Cod sursa (job #3194532) | Cod sursa (job #631215) | Cod sursa (job #2749942) | Cod sursa (job #547665) | Cod sursa (job #492861)
Cod sursa(job #492861)
#include <cstdio>
#include <cstdlib>
FILE *fin=fopen("lupu.in","r");
FILE *fout=fopen("lupu.out","w");
int n,x,lu;
int d[100000];
int l[100000];
int hp[100000];
int hpn;
inline bool hp_compare(int a,int b)
{
return l[hp[a]]>l[hp[b]];
}
inline void hp_swap(int a,int b)
{
hp[a]=hp[a]^hp[b];
hp[b]=hp[a]^hp[b];
hp[a]=hp[a]^hp[b];
}
void hp_up(int i)
{
while (i)
{
int pos = ((i+1)>>1)-1;
if (hp_compare(pos, i)) break;
hp_swap(pos, i);
i=pos;
}
}
void hp_down(int i)
{
while (1)
{
int pos1 = (i<<1)+1;
int pos2 = (i<<1)+2;
int max = i;
if ((pos1<hpn)&&(hp_compare(pos1, max)))
max=pos1;
if ((pos2<hpn)&&(hp_compare(pos2, max)))
max=pos2;
if (max==i) break;
hp_swap(max, i);
i=max;
}
}
void hp_create(int n)
{
hpn=n;
for (int i=hpn-1; i>=hpn/2; i--)
hp_up(i);
}
int hp_pop()
{
int rt = hp[0];
hp_swap(0, hpn-1);
hpn--;
hp_down(0);
return rt;
}
int main (int argc, char * const argv[]) {
fscanf(fin,"%d%d%d",&n,&x,&lu);
for (int i=0; i<n; i++)
{
fscanf(fin,"%d%d",&d[i],&l[i]);
hp[i]=i;
}
hp_create(n);
long long s = 0;
int dist = x;
for (int i=0; i<n; i++)
{
int pos = hp_pop();
if (d[pos]<=dist)
{
s+=l[pos];
dist-=lu;
}
}
fprintf(fout, "%lld\n",s);
fclose(fin);
fclose(fout);
return 0;
}