Cod sursa(job #436041)

Utilizator daniel.rizeaRizea Daniel daniel.rizea Data 8 aprilie 2010 00:56:57
Problema Gutui Scor 60
Compilator cpp Status done
Runda teme_upb Marime 2.47 kb
#include<stdio.h>
#include<list>
#include<stdlib.h>
using namespace std;
FILE* fin;
FILE* fout;

typedef struct gut{
    
    unsigned int inaltime;
    unsigned int greutate;
    unsigned int tmp;

}*gutui;
bool compare_desc(gut first,gut second)
{


  if (first.inaltime >= second.inaltime) return true;
  else return false;
}


int main(){

    unsigned int ** mat;
    
   unsigned int h,u,a,g,maxim;
    fin=fopen("gutui.in","r");
    fout=fopen("gutui.out","w");
    int n,i,j,max;
    int t;
    
    list<gut> cos;
    list<gut>::iterator it;

    
   
    fscanf(fin,"%d %d %d\n",&n,&h,&u);
 gut *aux;

 if(h%u==0)
 {
     t=0;
 max=h/u;

 }else
 {max=h/u+1;
 t=1;
 }
    for(i=0;i<n;i++)
    {
     aux=(gut*)malloc(sizeof(struct gut));
     

        fscanf(fin,"%u %u\n",&a,&g);
        
        if(a+(max-t-(a/u))*u<=h)
        
        aux->tmp=max-t-(a/u-1);
        else
            aux->tmp=max-t-(a/u);

        aux->inaltime=a;
        aux->greutate=g;
        cos.push_back(*aux);

    }

    cos.sort(compare_desc);

    for (it=cos.begin(); it!=cos.end(); ++it)
        printf("%u %u\n",it->greutate,it->inaltime);


   


    mat=(unsigned int**)malloc(sizeof(unsigned int*)*(n+1));
    it=cos.begin();

    
        
    
    

    
    for(i=0;i<=n;i++)
        mat[i]=(unsigned int*)malloc(sizeof(unsigned int)*(max+1));


    //it=cos.begin();

    //printf("%d %d\n",1,it->greutate);

        
           

    
  //  printf("max=%d\n",max);
    for(i=0;i<=n;i++)
    {if(i==1)
        it=cos.begin();

   // printf("i=%d tmp=%d\n",i,it->tmp);
        for(j=0;j<=max;j++)
        {

            if(i==0)
                mat[i][j]=0;
            else
                if(j==0)
                    mat[i][j]=0;
                else

                if(j>(int)(it->tmp))
                {mat[i][j]=mat[i][it->tmp];

                }
                else
                {
                maxim=mat[i-1][j];
               
               
               // printf("%d %d\n",j,it->greutate);
                

                if(maxim<mat[i-1][j-1]+it->greutate)
                   maxim=mat[i-1][j-1]+it->greutate;
                   
                mat[i][j]=maxim;

                }

        }
        ++it;
    }



    /*
    for(j=0;j<=max;j++)
        printf("%d ",j);
        printf("\n");

 for(i=0;i<=n;i++)
    {
for(j=0;j<=max;j++)
    printf("%d ",mat[i][j]);
  printf("\n");
 }
     */
       fprintf(fout,"%u",mat[n][max]);
        fclose(fin);
        fclose(fout);
        
    return 0;
}