Pagini recente » Cod sursa (job #196401) | Cod sursa (job #1938592) | Cod sursa (job #665684) | Cod sursa (job #2467617) | Cod sursa (job #1309511)
#include <algorithm>
#include <fstream>
using namespace std;
ifstream in("lupu.in");
ofstream out("lupu.out");
const int nmax = 100000;
int n , nh , x , l;
int d[nmax + 1] , a[nmax + 1] , v[nmax + 1] , h[nmax + 1];
int cmp(int i1 , int i2)
{
return (d[i1] > d[i2]);
}
void schimba(int i1 , int i2)
{
int aux = h[i1];
h[i1] = h[i2];
h[i2] = aux;
}
void urca(int i)
{
while(i >= 2 && h[i] > h[i / 2])
{
schimba(i / 2 , i);
i /= 2;
}
}
void coboara(int i)
{
int fs = 2 * i , fd = 2 * i + 1 , bun = i;
if(fs <= nh && h[bun] < h[fs])
bun = fs;
if(fd <= nh && h[bun] < h[fd])
bun = fd;
if(bun != i)
{
schimba(bun , i);
coboara(bun);
}
}
int main()
{
in >> n >> x >> l;
for(int i = 1 ; i <= n ; i++)
{
in >> d[i] >> a[i];
v[i] = i;
}
sort(v + 1 , v + n + 1 , cmp);
int indice = 1 , timp = 0;
long long s = 0;
nh = 0;
while(indice <= n)
{
if(x >= timp * l + d[v[indice]])
{
h[++nh] = a[v[indice]];
urca(nh);
timp++;
}
else
{
if(h[1] < a[v[indice]])
{
h[nh] = a[v[indice]];
urca(nh);
}
}
indice++;
}
for(int i = 1 ; i <= nh ; i++)
s += h[i];
out << s << '\n';
return 0;
}