Pagini recente » Cod sursa (job #1463594) | Cod sursa (job #3247886) | Cod sursa (job #2821416) | Cod sursa (job #1244615) | Cod sursa (job #441308)
Cod sursa(job #441308)
/*
Catalina Mihai Vlad
334CB
Problema - Gutui
Complexitate O(N^2)
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int main(void){
int N,H,U,G=0,*h,*g,*m,i,j,aux;
FILE *f;
f=fopen("gutui.in","r");
fscanf(f,"%i%i%i",&N,&H,&U);
h=(int*)malloc(sizeof(int)*N);//inaltimile gutuilor
g=(int*)malloc(sizeof(int)*N);//greutatile gutuilor
m=(int*)malloc(sizeof(int)*N);//aici marcam fiecare gutuie culeasa
memset(m,0,N*sizeof(int));//demarcam toate gutuile
for(i=0;i<N;i++)
fscanf(f,"%i%i",&h[i],&g[i]);
fclose(f);
for(i=0;i<N-1;i++)//sortare descrescatoare dupa inaltimi
for(j=i+1;j<N;j++)
if( h[i] < h[j] ){
aux = h[i];
h[i] = h[j];
h[j] = aux;
aux = g[i];
g[i] = g[j];
g[j] = aux;
}
aux=0;//aux va contoriza cate gutui au fost culese
for(i=0;i<N;i++)
if( h[i] + aux * U <= H ){
m[i] = 1;
G += g[i];
aux++;
}
else for(j=i-1;j>=0;j--)
if(m[j] && g[j] < g[i]){
m[i] = 1;
m[j] = 0;
G += g[i] - g[j];
}
//for(i=0;i<N;i++)
// if(m[i])
// printf("Cules gutuia de la inaltimea %3i cu greutatea %3i\n",h[i],g[i]);
f=fopen("gutui.out","w");
fprintf(f,"%i",G);
fclose(f);
return 0;
}