Cod sursa(job #436417)

Utilizator dragospDragos Pricope dragosp Data 8 aprilie 2010 16:11:47
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 1.39 kb
#include <stdio.h>
#include <stdlib.h>

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

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

int main() {
    unsigned 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);
        
    unsigned int currentpoz=0,currentweight,lasth;
    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;    
        }
    }
    
    unsigned int poz = 0, max_weight = 0, currenth = gutui[0].h, weight = 0,index=0;
    while(currenth <= H) {
         while(currenth+U > gutui[poz].h) {
            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 1;
}