Cod sursa(job #440411)

Utilizator buradaandreiBurada Andrei buradaandrei Data 12 aprilie 2010 00:43:31
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 1.14 kb
#include <stdio.h>
#include <stdlib.h>

typedef unsigned long long int uint64_t;

typedef struct gutui {
        uint64_t h,g;
    } Gutui;

int compare(const void* a, const void* b){
    return (((Gutui*)b)->h-((Gutui*)a)->h);
}
//cel mai greu care va disparea cel mai curand
/*int compare(const void* a, const void* b){
    return (((Gutui*)b)->g-((Gutui*)a)->g);
}*/

int main() {
    FILE *fi=fopen("gutui.in","r");
    FILE *fo=fopen("gutui.out","w");

    Gutui *g,ales;
    uint64_t n,i,j,total=0,h,u;

    fscanf(fi,"%llu %llu %llu",&n,&h,&u);
    g=(Gutui*)calloc(n,sizeof(Gutui));
    for (i=0;i<n;i++) {
        fscanf(fi,"%llu %llu",&g[i].h,&g[i].g);
    }

    qsort(g,n,sizeof(Gutui),compare);


    for (i=0;i<n;i++) {
        ales=g[i];
        if (g[i].h<=h) {
            h-=u;
            for (j=i+1;j<n;j++) {
                if (g[j].h>h) {
                    if (g[j].g>ales.g)
                        ales=g[j];
                }
                else break;
            }
        total+=ales.g;
        }
    }

    fprintf(fo,"%llu",total);
    fclose(fi);
    fclose(fo);
    return 0;
}