Pagini recente » Cod sursa (job #276477) | Cod sursa (job #2271326) | Cod sursa (job #1794295) | Cod sursa (job #98933) | Cod sursa (job #441380)
Cod sursa(job #441380)
/*
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,aux2;
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 {aux2=i;
for(j=i-1;j>=0;j--)
if(m[j] && g[j] < g[aux2])
aux2=j;
if(aux2!=i){
m[aux2]=0;
m[i] =1;
G += g[i] - g[aux2];
}
}
//for(i=0;i<N;i++){
// printf("\ngutuie la %3i greutate %3i stat: ",h[i],g[i]);
// if(m[i])
// printf("Culeasa!");
// else printf("neculeasa.");
//}printf("\n");
f=fopen("gutui.out","w");
fprintf(f,"%i",G);
fclose(f);
return 0;
}