Cod sursa(job #440436)

Utilizator buradaandreiBurada Andrei buradaandrei Data 12 aprilie 2010 01:05:07
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 1.69 kb
#include <stdio.h>
#include <stdlib.h>

typedef unsigned long long int uint64_t;

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

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

int compare2(const void* a, const void* b){
    return (((Gutui*)b)->g-((Gutui*)a)->g);
}

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

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

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

    fscanf(fi,"%llu %llu %llu",&n,&h,&u);
    g=(Gutui*)calloc(n,sizeof(Gutui));
    q=(uint64_t*)calloc(n,sizeof(uint64_t));
    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++)
        fprintf(fo,"%llu\t%llu\n",g[i].h,g[i].g);


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

    //dupa ce a ales incearca sa maximizeze suma
    //sortez crescator dupa greutate
    qsort(q,k,sizeof(uint64_t),compar2);
    //sortez descrescator dupa greutate
    qsort(g,n,sizeof(Gutui),compare2);

    for (i=0;i<n;i++)
        if (!g[i].cules)
            q[k2++]=g[i].g;

    for (i=0;i<k;i++)
        total+=q[i];

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