Pagini recente » Cod sursa (job #2614537) | Cod sursa (job #891103) | Cod sursa (job #725715) | Cod sursa (job #590720)
Cod sursa(job #590720)
#include <fstream.h>
#include <algorithm>
#define N 100005
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
struct oaie { int d,c; } v[N];
int n,T,i,H[N],k;
long long sol;
void citire() {
int i,X,L;
fin>>n>>X>>L; if (!L) L=1;
for (i=1;i<=n;i++)
{
fin>>v[i].d>>v[i].c;
if (v[i].d<=X) v[i].d=(X-v[i].d)/L;
else v[i].d=v[i].c=0;
}
}
int cmp (oaie a, oaie b)
{
return (a.d>b.d);
}
void upheap(int x) {
while (x>1 && H[x]>H[x/2])
{
swap (H[x], H[x/2]);
x/=2;
}
}
void downheap(int x) {
int fiu;
do
{
fiu=0;
if (2*x<=k) fiu=2*x;
if (2*x+1<=k && H[fiu]<H[fiu+1]) fiu=2*x+1;
if (H[x]>=H[fiu]) fiu=0;
if (fiu)
{
swap (H[x], H[fiu]);
x=fiu;
}
}
while (fiu);
}
int main() {
citire();
sort(v+1, v+n+1, cmp);
for (i=1, T=v[1].d; i<=n && T>=0; T--)
{
while (v[i].d>=T && i<=n)
{
H[++k]=v[i++].c;
upheap(k);
}
sol+=H[1];
swap (H[1], H[k--]);
downheap(1);
if (i>n)
i=n;
}
fout<<sol;
return 0;
}