Pagini recente » Cod sursa (job #385218) | Diferente pentru implica-te/arhiva-educationala intre reviziile 223 si 100 | Cod sursa (job #1760144) | Cod sursa (job #105958) | Cod sursa (job #441556)
Cod sursa(job #441556)
#include <stdio.h>
#include <vector>
#include <algorithm>
#define N 100000
using namespace std;
typedef struct {
unsigned long w, h, pos;
} quince;
unsigned long n, hmax, u;
vector<quince> v, heap;
void read() {
unsigned int i;
scanf("%lu %lu %lu", &n, &hmax, &u);
for ( i = 0; i < n; i++ ) {
quince e;
scanf("%lu %lu", &e.h, &e.w);
e.pos = (hmax - e.h)/u + 1;
v.insert(v.end(), e);
}
}
void print() {
unsigned int i;
for ( i = 0; i < v.size(); i++ )
printf("%lu %lu %lu\n", v[i].h, v[i].w, v[i].pos);
}
bool quinceCmpWeight (const quince q1, const quince q2) {
if (q1.w < q2.w)
return true;
return false;
}
bool quinceCmpHeight (const quince q1, const quince q2) {
if (q1.pos > q2.pos)
return true;
return false;
}
int main() {
unsigned long gmax = 0, minPos, i;
freopen("gutui.in", "r", stdin);
freopen("gutui.out", "w", stdout);
read();
sort(v.begin(), v.end(), quinceCmpHeight);
make_heap(heap.begin(), heap.end(), quinceCmpWeight);
minPos = v[0].pos;
heap.insert(heap.end(), v[0]);
push_heap(heap.begin(), heap.end(), quinceCmpWeight);
for ( i = 1; i < n; i++ ) {
if ( v[i].pos < v[i-1].pos )
for ( ; minPos > v[i].pos; minPos-- )
if(heap.size()) {
gmax += heap.front().w;
pop_heap(heap.begin(), heap.end(), quinceCmpWeight);
heap.pop_back();
}
heap.insert(heap.end(), v[i]);
push_heap(heap.begin(), heap.end(), quinceCmpWeight);
}
for ( ; minPos > 0 && heap.size(); minPos-- ) {
gmax += heap.front().w;
pop_heap(heap.begin(), heap.end(), quinceCmpWeight);
heap.pop_back();
}
printf("%lu\n", gmax);
return 0;
}