Cod sursa(job #437881)

Utilizator Th30dorGherghescu Teo Th30dor Data 10 aprilie 2010 10:34:06
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.79 kb
#include <stdio.h>
#include <stdio.h>
//#include <file.h>
#include <stdlib.h>
#include <queue>
using namespace std;


typedef struct gutuie{
	
	int h;
	int g;
	}gutuie;


int compareH (const void * a, const void * b)
{
	gutuie *ax = (gutuie * )a;  
	gutuie *bx = (gutuie *)b;
	return (*ax).h-(*bx).h;
//	return ( (*(int *)a).h-(*(int *)b).h );
}

int compareG (const void * a, const void * b)
{
	gutuie *ax = (gutuie * )a;  
	gutuie *bx = (gutuie *)b;
	return (*ax).g-(*bx).g;
//	return ( (*(int *)a).h-(*(int *)b).h );
}


int main(){

int N,H,U;

FILE *in;
FILE *out;
in = fopen("gutui.in","r");
out=fopen("gutui.out","w");
fscanf(in,"%d",&N);//nr de gutui
fscanf(in,"%d",&H);//inaltimea la care ajunge Gigel
fscanf(in,"%d",&U);//cu cat se ridica crengile

priority_queue< int, vector<int>, greater<int> > pq;


gutuie *vGut;//vectorul de gutui :D

vGut = (gutuie *)malloc(N*sizeof(gutuie));


//citire din fisier
for(int i=0;i < N;i++){
	fscanf(in,"%d",&vGut[i].h);
	fscanf(in,"%d",&vGut[i].g);

	}


qsort (vGut, N, sizeof(gutuie), compareH);//sortez vectorul de gutui

gutuie *aGut;//vector auxiliar de gutui
aGut = (gutuie *)malloc(N*sizeof(gutuie));


int copieH = H;
int copieN=N;

//int min=50000,pozMin=0;

int j=0;

//aGut[0]=vGut[N-1];

pq.push(vGut[N-1].g);

//int dimCrt=1;

copieH=copieH-U;

for(int i=N-2;i>=0;i--){
	/*min=50000;
	for(j=0;j<dimCrt;j++){
		if(aGut[j].g<min){
			min=aGut[j].g;
			pozMin=j;
			}
					
					
		}*/
	if(vGut[i].h<=copieH){
		//aGut[dimCrt]=vGut[i];
		//dimCrt++;
		pq.push(vGut[i].g);
		copieH=copieH-U;

					
		}

	else if(vGut[i].g>pq.top()){
		         //aGut[pozMin]=vGut[i];
			pq.pop();
			pq.push(vGut[i].g);						
				}
	}

int suma=0;
//for(int i=0;i < dimCrt;i++)
while(!pq.empty()){
	suma=suma+pq.top();
	pq.pop();	
	}
fprintf(out,"%d",suma);
fclose(in);
fclose(out);	
	

}