Pagini recente » Cod sursa (job #1872315) | Cod sursa (job #326026) | Cod sursa (job #959258) | Cod sursa (job #1753727) | Cod sursa (job #610820)
Cod sursa(job #610820)
#include <cstdio>
#include <algorithm>
#define NMAX 100000
using namespace std;
struct oaie
{
int nr, pas;
} t[NMAX];
int H[NMAX + 1], lh, a[NMAX], d[NMAX], n, x, l;
bool cmp(oaie x, oaie y)
{
return x.pas < y.pas;
}
void percolate(int i)
{
int curent = H[i];
while(i>1 && a[H[i/2]] < a[curent])
{
H[i] = H[i/2];
i /= 2;
}
H[i] = curent;
}
void stif(int i)
{
int st, dr, son;
do
{
st = 2*i;
dr = 2*i + 1;
son = 0;
if(st < lh)
{
son = st;
if(dr < lh && a[H[dr]] > a[H[st]])
{
son = dr;
}
if(a[H[son]] < a[H[i]])
{
son = 0;
}
}
if(son)
{
swap(H[i], H[son]);
}
i = son;
} while(son);
}
int main()
{
int tmax = 0, i, curent, ok;
long long sum = 0;
freopen("lupu.in", "r", stdin);
freopen("lupu.out", "w", stdout);
scanf("%d %d %d", &n, &x, &l);
//t[i].pas e numarul maxim de pasi dupa care poate fi prinsa oaia t[i].nr
for(i=0;i<n;++i)
{
scanf("%d %d", &d[i], &a[i]);
if(x - d[i] >= 0)
{
t[i].pas = (x - d[i]) / l + 1;
}
t[i].nr = i;
if(tmax < t[i].pas)
{
tmax = t[i].pas;
}
}
sort(t, t+n, cmp); //sortez dupa pas
i = n-1;
curent = tmax;
lh = 0; //lungimea heap-ului (initial e gol)
//parcurg t de la max la min
while(curent > 0)
{
ok = 1;
while(i >= 0 && t[i].pas == curent)
{
ok = 0;
H[++lh] = t[i].nr;
percolate(lh);
--i;
}
//extrag maximul
if(lh > 0)
{
sum += a[H[1]];
H[1] = H[lh--];
stif(1);
}
--curent;
}
printf("%lld", sum);
return 0;
}