Pagini recente » Cod sursa (job #2645239) | Cod sursa (job #352146) | Cod sursa (job #2113006) | Cod sursa (job #209375) | Cod sursa (job #3173407)
#include <bits/stdc++.h>
#define NN 100005
using namespace std;
ifstream fin ("lupu.in");
ofstream fout ("lupu.out");
struct Oi
{
int pasi, blana;
};
int n, dmax, lenpas;
int a, b, pasi, pasimax, suma, blana, hsize, h[NN];
Oi v[NN];
void push_up(int p)
{
int pp;
while(p != 1)
{
pp = p / 2;
if(h[pp] >= h[p])
return;
swap(h[p], h[pp]);
p = pp;
}
}
void push_down(int p)
{
int pp;
while(p * 2 <= hsize)
{
pp = p * 2;
if(pp + 1 <= hsize && h[pp + 1] > h[pp])
pp++;
if(h[pp] <= h[p])
return;
swap(h[p], h[pp]);
p = pp;
}
}
bool compara(Oi a, Oi b)
{
if(a.pasi > b.pasi)
return true;
if(a.pasi < b.pasi)
return false;
return a.blana > b.blana;
}
int main()
{
fin >> n >> dmax >> lenpas;
for(int i = 1 ; i <= n ; i++)
{
fin >> a >> v[i].blana;
v[i].pasi = 1 + (dmax - a) / lenpas;
pasimax = max(pasimax, v[i].pasi);
}
sort(v + 1, v + 1 + n, compara);
int k = 1;
while(pasimax > 0)
{
while(v[k].pasi == pasimax && k <= n)
{
hsize++;
h[hsize] = v[k].blana;
push_up(hsize);
k++;
}
if(hsize > 0)
{
suma += h[1];
h[1] = h[hsize];
h[hsize] = 0;
hsize--;
push_down(1);
}
pasimax--;
}
fout << suma;
return 0;
}