Cod sursa(job #436525)

Utilizator dragospDragos Pricope dragosp Data 8 aprilie 2010 17:18:18
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 1.35 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct s {
    int h,m;
} gutuie;

int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

int main() {
    int N, H, U;
    int i;
    FILE *fin = fopen("gutui.in","r");
    FILE *fout = fopen("gutui.out","w");
    fscanf(fin,"%d%d%d",&N,&H,&U);
    gutuie* gutui = (gutuie*) malloc(N*sizeof(gutuie));	
    
    for(i=0;i<N;i++)
        fscanf(fin,"%d%d",&(gutui[i]).h,&(gutui[i]).m);

	qsort (gutui, N, sizeof(gutuie), compare);   
    
    int currentweight,lasth;
	int currentpoz=0;    
	lasth = gutui[0].h;
    currentweight = gutui[0].m;
    
    for(i=1;i<N;i++) {
        if(gutui[i].h == lasth) {
            gutui[currentpoz].m+=gutui[i].m;
            gutui[i].m = 0;                    
        }
        else {
            currentweight = gutui[i].m;
            lasth = gutui[i].h;
            currentpoz = i;    
        }
    }  
    
	int poz=0; 
	int max_weight = 0, currenth = gutui[0].h, weight = 0; 
	while(currenth <= H) {
		 int inaltime = currenth+U;
         while(inaltime > gutui[poz].h && poz < N) {
            if(gutui[poz].m > max_weight) 
                max_weight = gutui[poz].m;
            poz++;   
         }
		currenth+=U;
		weight+=max_weight;
		max_weight = 0;
    }
    fprintf(fout,"%d\n",weight);
    return 0;
}