Pagini recente » Cod sursa (job #2115917) | Cod sursa (job #903386) | Cod sursa (job #249163) | Cod sursa (job #987717) | Cod sursa (job #440881)
Cod sursa(job #440881)
#include <stdio.h>
#include <fstream>
#include <iostream>
#include <stdlib.h>
#include <vector>
#include <queue>
using namespace std;
class gutui_t {
public:
int h;
int g;
public:
gutui_t(int hval, int gval);
gutui_t(){
h = 0;
g = 0;
}
~gutui_t(){}
bool operator<(const gutui_t&) const;
};
gutui_t::gutui_t (int hval, int gval){
h = hval;
g = gval;
}
bool gutui_t::operator<(const gutui_t& snd) const
{
return g < snd.g;
}
int comp( const void* x, const void* y){
gutui_t fst = *(gutui_t*)x;
gutui_t snd = *(gutui_t*)y;
return snd.h - fst.h;
}
int main(){
FILE *f=stdin,*out=stdout;
int n, hmax, u, i, first = 1, level = 1, val = 0;
gutui_t gutuie;
f = fopen("gutui.in", "r");
out= fopen("gutui.out", "w");
//citire
fscanf(f,"%d %d %d",&n, &hmax, &u);
gutui_t *v = (gutui_t *)calloc(n, sizeof(gutui_t));
priority_queue <gutui_t> pq;
for (i = 0 ; i < n ;i ++){
fscanf(f,"\n");
fscanf(f, "%d %d", &gutuie.h, &gutuie.g);
if( gutuie.h <= hmax){
//gutuie.l = (hmax - gutuie.h) / u + 1;
v[i] = gutuie;
}
}
//for(i = 0 ; i < n ;i++)
// printf("%d %d \n",v[i].h, v[i].g);
//printf("\n Quick Sort\n");
//ordonare dupa greutate
//quicksort(v,0,n-1); //O(nlogn) in cazul mediu...O(n^2) in cel mai rau caz...voi lua in considerare cazul mediu
qsort(v, n, sizeof(gutui_t), comp);
//for(i = 0 ; i < n ;i++)
// printf("%d %d \n",v[i].h, v[i].g);
//printf("\n n = %d\n", n);
for(i = 0 ; i < n ;){
if( ( v[i].h + level * u) > hmax && first > 0){
pq.push(v[i]);
first --;
i++;
}
else if( (v[i].h + level * u) > hmax && !first){
gutuie = pq.top();
if(v[i].g > gutuie.g){
pq.pop();
pq.push(v[i]);
}
i++;
}
else{
level++;
first++;
}
}
//printf("am iesit\n");
while(!pq.empty()){
gutuie = pq.top();
val+=gutuie.g;
pq.pop();
}
fprintf(out, "%d", val);
fclose(f);
fclose(out);
return 0;
}