Cod sursa(job #430416)

Utilizator Cristina_89Cristina Savin Cristina_89 Data 30 martie 2010 23:47:47
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 1.37 kb
#include <stdio.h>
#include <stdlib.h>



int *hh,*gg,*pus;
int n,h,u,crt;
#define CRESC 10
void sort()
{
     int i,j,t;
     for(i=0;i<n-1;i++)
        for (j=i+1;j<n;j++)
            if (hh[i]>hh[j]) {t=hh[i];hh[i]=hh[j];hh[j]=t;
                              t=gg[i];gg[i]=gg[j];gg[j]=t; }  
     
}

int maxim(int pasi)
{
    int ok=0,max=-1,poz=-1,i;
    for (i=crt;i>=0;i--)
        if (!pus[i] && (hh[i]+u*pasi)<=h)
        {  
           ok=1;
           if (hh[i]+u*(pasi+1)<=h) break;
           else 
                if (gg[i]>max) {max=gg[i];poz=i;}
        }
    if (!ok) return -1;
    if (poz==-1) poz=i;
    crt=i;
    pus[poz]=1;
	
	printf("Aleg gg=%d\n",gg[poz]);
	return gg[poz];    
}
    
    
int main()
{
    int i;
    FILE *fis=fopen("gutui.in","r");
    fscanf(fis,"%d%d%d",&n,&h,&u);

    hh=(int*)malloc(n*sizeof(int));
    gg=(int*)malloc(n*sizeof(int));
    pus=(int*)malloc(n*sizeof(int));
    
    for(i=0;i<n;i++)
       {fscanf(fis,"%d%d",&hh[i],&gg[i]);pus[i]=0;}
    fclose(fis);
    
    sort();
    
    int pasi=0;
    int gr=0;
    int tmp;
    crt=n-1;
    while(1)
    {
         tmp=maxim(pasi);
         if (tmp<0) break;
         gr+=tmp;
         pasi++;
    }            
    FILE *fis1=fopen("gutui.out","w");
    fprintf(fis1,"%d\n",gr);
    fclose(fis1);
    
    return 0;   
}