Pagini recente » Profil erics16 | Cod sursa (job #2013895) | Cod sursa (job #3124568) | Profil vacduzz | Cod sursa (job #439639)
Cod sursa(job #439639)
#include<stdio.h>
#include<stdlib.h>
#define N 100000
FILE *fin, *fout;
long long int n,h,u;
long long int aleg[N];
/* structura de tip gutuie care contine greutatea gutuii si nivelul la care se afla*/
typedef struct gutuie{
long long int nv;//nivel
long long int g; //greutate
} Gutuie;
Gutuie *pom;//variabila pom contine toate gutuile de tipul structura
//functie comparare pentru qsort
int comp(const void * a, const void * b) {
if ((*(Gutuie*) b).nv - (*(Gutuie*) a).nv < 0) return -1;
else
if ((*(Gutuie*) b).nv - (*(Gutuie*) a).nv == 0) return 0;
else
return 1;
}
int main(void)
{
/* fisiere intrare iesir */
fin = fopen("gutui.in", "r");
fout = fopen("gutui.out", "w");
long long int i,j;
long long int inaltimegutuie;
//citire N H U din fisier
fscanf(fin, "%lld %lld %lld", &n, &h, &u);
printf("%lld %lld %lld\n \n",n,h,u);
//alocare memorie
pom=(Gutuie *) calloc (n,sizeof(struct gutuie));
//citirea pomului din fisier
for (i = 0; i < n; i++) {
//citesc din fisier inaltime gutuie + greutate
fscanf(fin, "%lld %lld", &inaltimegutuie, &(pom[i].g));
//transform inaltime gutuie + inaltime pas in nivel
pom[i].nv=(h-inaltimegutuie)/u + 1;
}
//sortez in functie de nivel
qsort(pom,n,sizeof(struct gutuie),comp);
long long int pas=0;
long long int aleg[n],min,ales;
long long int suma=0;
for(i=n-1;i>=0;i--)
{
//daca pas < nivelul curent atunci trec la nivelul curent si aleg prima gutuie de pe nivelul vurent
if( pas < pom[i].nv )
{
pas ++;
aleg[pas]=pom[i].g;
}
else
//daca pas = nivelul curent atunci caut sa maximizez vectorul de alegeri prin inlocuirea
//greutatii minime din vect de alegeri cu greutatea maxima de pe nivelul curent
if ( pas == pom[i].nv )
{
min=aleg[pas];
ales=pas;
//caut minim in vectorul de alegeri
for(j=1;j<=pas;j++)
if( min > aleg[j] ) { min=aleg[j];ales=j; }
//inlocuiesc daca pe niv curent am gutuie mai mare decat in minimul din vect de alegeri
if(pom[i].g > aleg[ales]) aleg[ales]=pom[i].g;
}
}
//calculez suma maxma adunand cele mai bune alegeri
for(i=1;i<=pas;i++)
suma=suma+aleg[i];
//printez solutia
fprintf(fout,"%lld\n",suma);
fclose(fin);
fclose(fout);
return 0;
}