Pagini recente » Cod sursa (job #928355) | Cod sursa (job #2954294) | Cod sursa (job #463061) | Cod sursa (job #2037823) | Cod sursa (job #463123)
Cod sursa(job #463123)
#include<stdio.h>
#include<stdlib.h>
#define MAX 100001
using namespace std;
#include<queue>
typedef struct _gutuie{
long int h, g;
}gutuie;
//functia de comparare pentru sortare descrescatoare
int compare (const void* a, const void* b)
{
if((*(gutuie*)a).h == (*(gutuie*)b).h)
return ((*(gutuie*)a).g - (*(gutuie*)b).g);
else
return -((*(gutuie*)a).h - (*(gutuie*)b).h);
}
int main()
{
//declarari, citiri si alocari
FILE * in = fopen("gutui.in", "r");
FILE * out = fopen("gutui.out", "w");
long int N, H, U, i;
fscanf(in, "%ld %ld %ld", &N, &H, &U);
gutuie *gut;
gut = (gutuie*) malloc (sizeof(gutuie) * N);
priority_queue<long int> q;
for(i = 0; i < N; i++)
fscanf(in,"%ld %ld", &gut[i].h, &gut[i].g);
qsort(gut, N, sizeof(gutuie), compare);
unsigned int nrgut = (H - gut[0].h) / U + 1;
q.push(-gut[0].g); //simulez un heap minim (maximul dintre -7 si -9 este -7, deci o sa am in coada -7, -9; cand afisez, scot minusul)
//explic algoritmul pas cu pas in Readme
for(i = 1; i < N; i++)
{
nrgut = (H - gut[i].h) / U + 1;
if(nrgut > q.size())
q.push(-gut[i].g);
else
if(nrgut == q.size() && -q.top() < gut[i].g)
{
q.pop();
q.push(-gut[i].g);
}
}
//adun valorile din q
long int cont = 0;
while(!q.empty())
{
// printf("%d\n", -q.top());
cont+= -q.top();
q.pop();
}
fprintf(out,"%ld\n", cont);
return 0;
}