Pagini recente » Cod sursa (job #2271428) | Cod sursa (job #2960507) | Cod sursa (job #2803545) | Cod sursa (job #411990) | Cod sursa (job #462981)
Cod sursa(job #462981)
/**
* NUME: CARBUNE VICTOR
* GRUPA: 325 CA
* PROBLEMA: GUTUI
*
*/
#include <vector>
#include <stdio.h>
#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);
}
}
/* Compararea gutuilor dupa greutate */
bool quinceCmpWeight (const quince q1, const quince q2) {
if (q1.w < q2.w)
return true;
return false;
}
/* Compararea gutuilor dupa nivel / pozitie */
bool quinceCmpPos (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();
//complexitate O(NlogN) -- sortare
sort(v.begin(), v.end(), quinceCmpPos);
minPos = v[0].pos;
heap.push_back(v[0]);
push_heap(heap.begin(), heap.end(), quinceCmpWeight);
//complexitate O(NlogN) -- for + inserare in heap
for ( i = 1; i < n; i++ ) { //O(N)
//daca se intalneste o gutuie cu un nivel diferit de cel curent
//se scot din heap un numar de gutui egale cu diferenta de nivel
if ( v[i].pos < v[i-1].pos )
while ( minPos > v[i].pos ) {
if(heap.size()) {
gmax += heap.front().w;
pop_heap(heap.begin(), heap.end(), quinceCmpWeight); //O(logN)
heap.pop_back();
}
minPos--;
}
//se insereaza gutuia in heap
heap.push_back(v[i]);
push_heap(heap.begin(), heap.end(), quinceCmpWeight); //O(logN)
}
//daca heap-ul nu este gol, si mai sunt pasi disponibili, se scot din heap
while ( minPos > 0 && heap.size() ) {
gmax += heap.front().w;
pop_heap(heap.begin(), heap.end(), quinceCmpWeight);//O(logN)
heap.pop_back();
minPos--;
}
printf("%lu\n", gmax);
return 0;
}