Pagini recente » Cod sursa (job #1275494) | Cod sursa (job #1174659) | Cod sursa (job #2473159) | Cod sursa (job #1005375) | Cod sursa (job #2289817)
#include <iostream>
#include <fstream>
#define MAX 100001
std::ifstream f("lupu.in");
std::ofstream g("lupu.out");
struct oaie {
int distance;
int wool;
};
oaie v[MAX];
///Begin of quickSort
int partition(int left, int right) {
int i = left;
int j = right;
oaie pivot = v[(left + right) / 2];
while (i <= j) {
while (v[i].distance < pivot.distance || (v[i].distance == pivot.distance && v[i].wool > pivot.wool))
++i;
while (v[j].distance > pivot.distance || (v[j].distance == pivot.distance && v[j].wool < pivot.wool))
--j;
if (i <= j) {
std::swap(v[i], v[j]);
++i;
--j;
}
}
return i;
}
void quickSort(int left, int right) {
int index = partition(left, right);
if (left < index - 1)
quickSort(left, index - 1);
if (index < right)
quickSort(index, right);
}
///End of quickSort
class MaxHeap {
private:
int size;
oaie h[MAX];
int father(int node) {
return node / 2;
}
int leftSon(int node) {
return node * 2;
}
int rightSon(int node) {
return node * 2 + 1;
}
void sift(int k) {
int son;
do {
son = 0;
int lSon = leftSon(k);
if (lSon <= size) {
son = lSon;
int rSon = rightSon(k);
if (rSon <= size && h[rSon].wool > h[lSon].wool) {
son = rSon;
}
if (h[son].wool <= h[k].wool) {
son = 0;
}
}
if (son) {
std::swap(h[son], h[k]);
k = son;
}
} while (son);
}
void percolate(int k) {
oaie key = h[k];
int kFather = father(k);
while (k > 1 && key.wool > h[kFather].wool) {
h[k] = h[kFather];
k = kFather;
kFather = father(k);
}
h[k] = key;
}
public:
MaxHeap(int size) {
this->size = size;
}
int getMax() {
return h[1].wool;
}
int getSize() {
return this->size;
}
void insert(oaie value) {
h[++size] = value;
percolate(size);
}
void remove(int position) {
h[position] = h[size];
--size;
if (position > 1 && h[position].wool > h[father(position)].wool)
percolate(position);
else
sift(position);
}
};
int main() {
int n;
f >> n;
int x;
f >> x;
int l;
f >> l;
for (int i = 1; i <= n; ++i) {
f >> v[i].distance >> v[i].wool;
}
quickSort(1, n);
MaxHeap* h = new MaxHeap(0);
int sol = 0;
for (int dmax = x % l, i = 1; dmax <= x; dmax += l) {
for (; v[i].distance <= dmax && i <= n; ++i) {
h->insert(v[i]);
}
if (h->getSize()) {
sol += h->getMax();
h->remove(1);
}
}
g << sol << '\n';
return 0;
}