Cod sursa(job #440108)
Utilizator | Data | 11 aprilie 2010 21:59:32 | |
---|---|---|---|
Problema | Gutui | Scor | 10 |
Compilator | c | Status | done |
Runda | teme_upb | Marime | 2.15 kb |
#include<stdio.h>
#define MAX 10000
unsigned int alt[MAX];
unsigned int kg[MAX];
int N;
unsigned int U, H;
int tot[MAX]; //gutui culese
int nrc; //nr gutui culese
int minim(){
int i;
int min=0;
for(i=1;i<nrc;i++){
if(kg[tot[i]]<kg[tot[min]])
min=i;
}
return min;
}
int main(){
FILE *f;
f=fopen("gutui.in","r");
fscanf(f,"%d",&N);
fscanf(f,"%d",&H);
fscanf(f,"%d",&U);
int i,j;
unsigned int aux;
for(i=0;i<N;i++){
fscanf(f,"%d",&alt[i]);
fscanf(f,"%d",&kg[i]);
}
for(i=0;i<N-1;i++)
for(j=i+1;j<N;j++)
{
if(alt[i]<alt[j])
{
aux=alt[i];
alt[i]=alt[j];
alt[j]=aux;
aux=kg[i];
kg[i]=kg[j];
kg[j]=aux;
}
}
unsigned int hmax=H;
nrc=0;
for(i=0;i<N;i++){
if(alt[i]<=hmax){
tot[nrc++]=i;
hmax-=U;
}
else
{
j=minim(); //elementul j din tot[] are greutatea minima
if(kg[i]>kg[j])
tot[j]=i;
}
}
unsigned int total=0;
for(i=0;i<nrc;i++){
total += kg[tot[i]];
}
FILE* g;
g=fopen("gutui.out","w");
fprintf(g,"%d",total);
fclose(f);
fclose(g);
return 0;
}