Cod sursa(job #441093)

Utilizator elena.cavalCaval Elena elena.caval Data 12 aprilie 2010 19:15:55
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 1.75 kb
#include<stdio.h>
#include<stdlib.h>

typedef struct{
	int inaltime_gutuie;
	int greutate_gutuie;
}gutuie;

int inaltime_maxima,inaltime_crengi;

int compare_greutate(const void* a,const void *b)
{
    gutuie *ia = (gutuie *)a;
    gutuie *ib = (gutuie *)b;
    if (ib->greutate_gutuie == ia->greutate_gutuie)
        return ib->inaltime_gutuie-ia->inaltime_gutuie;
    return ib->greutate_gutuie-ia->greutate_gutuie;
}

int main()
{
    FILE *fin = fopen("gutui.in","r");
    FILE *fout = fopen("gutui.out","w");
    gutuie g[100000];
	int nr_gutui,inaltime_maxima,nr_elem_vector=0,nivel;
	int i,j,greutate_maxima=0;
	int vector[100000]={0};
	fscanf(fin,"%d",&nr_gutui);
	fscanf(fin,"%d",&inaltime_maxima);
	fscanf(fin,"%d",&inaltime_crengi);
	for(i=0;i<nr_gutui;i++)
	{
		fscanf(fin,"%d",&g[i].inaltime_gutuie);
		fscanf(fin,"%d",&g[i].greutate_gutuie);
	}
    qsort(g,nr_gutui,sizeof(gutuie),compare_greutate);
    int trecut;
    for(i=0;i<nr_gutui;i++)
    {
        trecut=0;
        nivel=(inaltime_maxima-g[i].inaltime_gutuie)/inaltime_crengi+1;
        if(vector[nivel]==0)
        {
            vector[nivel]=g[i].greutate_gutuie;
            nr_elem_vector++;
            trecut=1;
        }
        if(vector[nivel]!=0 && trecut==0)
        {
            for(j=nivel;j>=1;j--)
                if(vector[j]==0)
                {
                    vector[j]=g[i].greutate_gutuie;
                    nr_elem_vector++;
                    break;
                }
        }
    }
    int nr=1;
    for(i=1;nr<=nr_elem_vector;i++)
    {
        greutate_maxima+=vector[i];
        if(vector[i]!=0)
            nr++;

    }
    fprintf(fout,"%d",greutate_maxima);
    fclose(fout);
    fclose(fin);
    return 0;
}