Cod sursa(job #435464)

Utilizator mataevsMatei Chiperi mataevs Data 7 aprilie 2010 15:03:16
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 1.08 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

typedef struct {
	unsigned int ht;
	unsigned int g;
	int ns;
}elem;

int comp(const void *a, const void *b){
	elem *p1 = (elem*)a;
	elem *p2 = (elem*)b;
	if (p1->g < p2->g)
		return 1;
	if (p1->g > p2->g)
		return -1;
	return 0;
}

int main(){
	unsigned int n,h,u;
	int i,j;
	elem *gutui, *p;
	char *secv;
	int g = 0;
	
	FILE *fin = fopen("gutui.in", "r");
	fscanf(fin,"%d %d %d",&n,&h,&u);
	gutui = (elem*)malloc(n * sizeof(elem));
	for (p = gutui, i = 0; i < n; i++, p++){
		fscanf(fin,"%d %d", &(p->ht), &(p->g));
		p->ns = (h - p->ht) / u + 1;
	}
	fclose(fin);
	
	qsort(gutui, n, sizeof(elem),comp);
	
	secv = (char*)malloc((n + 1) * sizeof(char));
	memset(secv, 0, (n + 1) * sizeof(char));
	
	for (p = gutui, i = 0; i < n; i++, p++){
		for (j = p->ns; j > 0 && *(secv + j) == 1; j--);
		if (j > 0){
			*(secv + j) = 1;
			g += p->g;
		}
	}

	free(secv);
	free(gutui);
	
	FILE *fout = fopen("gutui.out", "w");
	fprintf(fout, "%d\n", g);
	fclose(fout);
	return 0;
}