Pagini recente » Cod sursa (job #449852) | Cod sursa (job #3136994) | Cod sursa (job #555789) | Cod sursa (job #1617064) | Cod sursa (job #2036183)
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct oaie{
int cant;
int strat;
};
int n,x,st,l,i,j,d,a,nrel,h[100005];
long long total;
oaie v[100005];
bool cmp(oaie a, oaie b)
{
if (a.strat<b.strat) return 1;
else return 0;
}
void urca()
{
int poz=nrel;
while (poz>1 && h[poz]>h[poz/2])
{
swap(h[poz],h[poz/2]);
poz=poz/2;
}
}
void coboara()
{
int poz=1,fiu;
while (2*poz<=nrel)
{
fiu=poz;
if (h[2*poz]>h[poz])
fiu=2*poz;
if (2*poz+1<=nrel && h[2*poz+1]>h[fiu])
fiu=2*poz+1;
if (fiu!=poz)
{
swap(h[poz],h[fiu]);
poz=fiu;
} else break;
}
}
int main()
{
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
scanf("%d%d%d",&n,&x,&l);
for (i=1; i<=n; i++)
{
scanf("%d%d",&d,&a);
v[i].cant=a;
v[i].strat=(d+l-1)/l;
}
sort(v+1,v+n+1,cmp);
j=1;
for (i=0; i<=x/l; i++)
{
//iau toate oile de pe stratul al i-lea si le bag in heap
while (j<=n && v[j].strat==i)
{
h[++nrel]=v[j++].cant;
urca();
}
if (nrel>0) {total=total+1ll*h[1];
h[1]=h[nrel--];}
coboara();
}
printf("%lld\n",total);
return 0;
}