Pagini recente » Cod sursa (job #2102570) | Cod sursa (job #797928) | Cod sursa (job #715532) | Cod sursa (job #960492) | Cod sursa (job #3143124)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
const int SHEEP_MAX = 1e5;
template<typename T>
class Heap{
private:
T heap[SHEEP_MAX];
int heapSize;
inline int parent(int i){
return (i - 1) / 2;
}
inline int leftChild(int i){
return 2 * i + 1;
}
inline int rightChild(int i){
return 2 * i + 2;
}
void upHeap(int i){
while(i && heap[i] < heap[parent(i)]){
swap(heap[i], heap[parent(i)]);
i = parent(i);
}
}
void downHeap(int i){
int smallest = i, left = leftChild(i), right = rightChild(i);
if(left < heapSize && heap[left] < heap[smallest])
smallest = left;
if(right < heapSize && heap[right] < heap[smallest])
smallest = right;
if(smallest != i){
swap(heap[i], heap[smallest]);
downHeap(smallest);
}
}
public:
Heap(){
heapSize = 0;
}
void insert(T x){
heap[heapSize++] = x;
upHeap(heapSize - 1);
}
T query(){
return heap[0];
}
void extractRoot(){
swap(heap[0], heap[heapSize - 1]);
--heapSize;
downHeap(0);
}
void clear(){
heapSize = 0;
}
};
struct Sheep{
unsigned int wool, distance;
friend ifstream& operator>>(ifstream& fin, Sheep& s){
fin >> s.distance >> s.wool;
return fin;
}
friend ofstream& operator<<(ofstream& fout, const Sheep& s){
fout << s.distance << ' ' << s.wool << '\n';
return fout;
}
};
struct unsignedint{
unsigned int x;
bool operator<(const unsignedint& other) const{
return x > other.x;
}
};
Sheep v[SHEEP_MAX + 1];
Heap<unsignedint> maxHeap;
bool cmp(const Sheep& a, const Sheep& b){
if(a.distance == b.distance)
return a.wool > b.wool;
return a.distance > b.distance;
}
int main(){
unsigned int sheep, x, l, n = 0;
fin >> sheep >> x >> l;
for(int i = 0; i < sheep; ++i){
Sheep aux;
fin >> aux;
if(aux.distance <= x){
aux.distance = (x - aux.distance) / l + 1;
v[n++] = aux;
}
}
return 0;
sort(v, v + n, cmp);
int j = 0;
long long sum = 0;
v[n].distance = 0;
for(unsigned int i = v[0].distance; i > 0; --i){
while(v[j].distance == i){
maxHeap.insert({v[j].wool});
++j;
}
sum += maxHeap.query().x;
maxHeap.extractRoot();
}
fout << sum << '\n';
fin.close();
fout.close();
return 0;
}