Cod sursa(job #440173)

Utilizator Th30dorGherghescu Teo Th30dor Data 11 aprilie 2010 22:32:45
Problema Gutui Scor 60
Compilator cpp Status done
Runda teme_upb Marime 2.31 kb
#include<stdlib.h>
#include<stdio.h>

long partition(long v[2][100000],long left,long right,long index)
{
    long pivotValue=v[0][index];
    long aux,i;
    
    aux=v[0][right];
    v[0][right]=v[0][index];
    v[0][index]=aux;
    
    aux=v[1][right];
    v[1][right]=v[1][index];
    v[1][index]=aux;

    long storeIndex=left;
    for (i=left;i<right;i++)
        if (v[0][i]>pivotValue)
           {
           aux=v[0][i];
           v[0][i]=v[0][storeIndex];
           v[0][storeIndex]=aux;
           
           aux=v[1][i];
           v[1][i]=v[1][storeIndex];
           v[1][storeIndex]=aux;
           
           storeIndex++;         
           }
    
    aux=v[0][storeIndex];
    v[0][storeIndex]=v[0][right];
    v[0][right]=aux;
    
    aux=v[1][storeIndex];
    v[1][storeIndex]=v[1][right];
    v[1][right]=aux;
    
    return storeIndex;
}

void quicksort(long v[2][100000],long left,long right)
{
     long pivot,pivotNew;
     if (left<right)
        {
        pivot=(left+right)/2;
        pivotNew=partition(v,left,right,pivot);
        quicksort(v,left,pivotNew-1);
        quicksort(v,pivotNew+1,right);
        }
}



int main()
{
    FILE *f,*o;
    f=fopen("gutui.in","r");
    o=fopen("gutui.out","w");
    
    long N,H,U;
    
    fscanf(f,"%li",&N);
    fscanf(f,"%li",&H);
    fscanf(f,"%li",&U);
    
    long i=0,g,h;
    long v[2][100000],sol[100000];
        
    while (fscanf(f,"%li%li",&h,&g)!=EOF)
          {
          v[0][i]=h;
          v[1][i]=g;
          i++;
          }
    quicksort(v,0,N-1);
    
    //for (i=0;i<N;i++)
        //fprintf(o,"%i %i\n",v[0][i],v[1][i]);
    long H2=H,k=0,min,j,poz;
    for (i=0;i<N;i++)
        {
        if (v[0][i]<=H2)
           {
           sol[k]=v[1][i];
           k++;
           H2=H2-U;
           }
        else
            {
            min=sol[0];
            for (j=0;j<k;j++)
                if (sol[j]<min)
                   {
                   min=sol[j];
                   poz=j;
                   }
            if (v[1][i]>min)
               sol[poz]=v[1][i];
            }
        }
    long sum=0;
    for (j=0;j<k;j++)
        sum=sum+sol[j];
    
    fprintf(o,"%li\n",sum);
    
    fclose(f);
    fclose(o);
    
    return 0;
}