Pagini recente » Cod sursa (job #2612908) | Cod sursa (job #2789418) | Cod sursa (job #300247) | Cod sursa (job #2738907) | Cod sursa (job #1303201)
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N = 1e5 + 10;
struct oaie{
int dist, cant, timp;
}a[MAX_N];
int heap[MAX_N], lgheap;
bool cmp(oaie x, oaie y){
if(x.timp >= y.timp){
x.cant = x.cant + y.cant - (y.cant = x.cant);
x.dist = x.dist + y.dist - (y.dist = x.dist);
return 0;
}
return 1;
}
void addheap(int i){
heap[++lgheap] = i;
int fiu = lgheap, tata = fiu / 2;
bool e = true;
while(tata >= 1 && e){
e = false;
if(a[heap[fiu]].cant > a[heap[tata]].cant){
heap[fiu] = heap[fiu] + heap[tata] - (heap[tata] = heap[fiu]);
fiu = tata;
tata = fiu / 2;
e = true;
}
}
}
int extractmax(){
int aux = a[heap[1]].cant;
heap[1] = heap[lgheap];
--lgheap;
int tata = 1, fiu = 2;
bool e = true;
while(fiu <= lgheap && e){
e = false;
if(a[heap[fiu + 1]].cant > a[heap[fiu]].cant && fiu + 1 <= lgheap)
++fiu;
if(a[heap[tata]].cant < a[heap[fiu]].cant){
heap[fiu] = heap[fiu] + heap[tata] - (heap[tata] = heap[fiu]);
tata = fiu;
fiu = tata * 2;
e = true;
}
}
return aux;
}
int main()
{
freopen("lupu.in", "r", stdin);
int n, x, l;
scanf("%d %d %d\n", &n, &x, &l);
for(int i = 1; i <= n; ++i){
scanf("%d %d", &a[i].dist, &a[i].cant);
a[i].timp = (x - a[i].dist) / l + 1;
}
fclose(stdin);
sort(a + 1, a + n + 1, cmp);
freopen("lupu.out", "w", stdout);
long long sol = 0;
for(int i = n; i >= 1; --i){
addheap(i);
if(a[i].timp != a[i - 1].timp && lgheap > 0)
for(int j = 1; j <= a[i].timp - a[i - 1].timp && lgheap > 0; ++j)
sol += extractmax();
}
printf("%lld", sol);
fclose(stdout);
return 0;
}