Cod sursa(job #439822)

Utilizator kp_itchyAlexandra kp_itchy Data 11 aprilie 2010 19:34:14
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.94 kb
#include<stdio.h>
#include<vector>
#include<algorithm>


using namespace std;

typedef struct {
	int greutate;
	int inaltime;
} gutuie;

//typedef unsigned int int;

//interschimba 2 elemente din vectorul de gutui
void swap(gutuie *a, gutuie *b) {
	gutuie aux;
	aux=*a;
	*a=*b;
	*b=aux;
}

//auxiliar pentru functia de sortare quicksort
int choose_pivot(int i, int j) {
	return ((i+j)/2);
}

//sorteaza descrescator in functie de greutate in vectorul de gutui
void qsort(gutuie *g, int m, int n) {	
	int key,i,j,k;
	if (m<n)
		{
			k=choose_pivot(m,n);
			swap(&g[m],&g[k]);
			key=g[m].inaltime;
			i=m+1;
			j=n;
			while (i<=j)
				{
				while ((i<=n)&&(g[i].inaltime>=key))
					i++;
				while ((j>=m) &&(g[j].inaltime<key))
					j--;
				if (i<j)
					swap(&g[i],&g[j]);
				}
			swap(&g[m],&g[j]);
			qsort(g,m,j-1);
			qsort(g,j+1,n);
		}
	}

bool sortareDupaGreutate(gutuie a, gutuie b) {
	return (a.greutate>b.greutate);
	}
	
int main() {
	int n,h,u,i,gt=0;
	FILE *in=fopen("gutui.in","r");
	FILE *out=fopen("gutui.out","w");
	vector<gutuie> heap;
		
	fscanf(in,"%u%u%u",&n,&h,&u);
	
	//alocare memorie
	gutuie *g=(gutuie*)malloc(n*sizeof(gutuie));
	
	//citire date fisier
	for (i=0;i<n;i++)
		fscanf(in,"%u%u",&g[i].inaltime,&g[i].greutate);
	/*
	for (i=0;i<n;i++)
		printf("%u %u\n",g[i].inaltime,g[i].greutate);
	printf("\n");
	*/
	qsort(g,0,n-1);
	/*
	for (i=0;i<n;i++)
		printf("%u %u\n",g[i].inaltime,g[i].greutate);
	printf("\n");
	*/
	heap.push_back(g[0]);
	
	for (i=1;i<n;i++) {
		if (heap.size()==(1+(h-g[i].inaltime)/u) && heap.front().greutate<g[i].greutate) {
			pop_heap(heap.begin(),heap.end(),sortareDupaGreutate);
			heap.pop_back();
			heap.push_back(g[i]);
			push_heap(heap.begin(),heap.end(),sortareDupaGreutate);
		}
		else if (heap.size()!=(1+(h-g[i].inaltime)/u)) {
				heap.push_back(g[i]);
				push_heap(heap.begin(),heap.end(),sortareDupaGreutate);
		}
	}
	
	for (i=0;i<heap.size();i++)
		gt+=heap[i].greutate;
	
	fprintf(out,"%u\n",gt);	
	
	return 0;
	}