Cod sursa(job #438442)

Utilizator p1tagoraCalin Pelcea p1tagora Data 10 aprilie 2010 19:29:49
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 2.2 kb
#include<stdlib.h>
#include<stdio.h>

int partition(int v[2][100000],int left,int right,int index)
{
    int pivotValue=v[0][index];
    int 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;

    int 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(int v[2][100000],int left,int right)
{
     int 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");
    
    int N,H,U;
    
    fscanf(f,"%i",&N);
    fscanf(f,"%i",&H);
    fscanf(f,"%i",&U);
    
    int i=0,g,h,j=0;
    int v[2][100000],mark[100000];
        
    while (fscanf(f,"%i%i",&h,&g)!=EOF)
          {
          v[0][i]=h/U;
          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]);
    int max=0,pmax,sum=0,H2=0;
    for (i=0;i<N;i++)
        {
        max=0;
        if (v[0][i]>v[0][i-1] || i==N-1)
           {
           for (j=0;j<i;j++)
               if (v[1][j]>max && mark[j]==0)
                  {
                  max=v[1][j];
                  pmax=j;
                  }
           sum=sum+max;
           mark[pmax]=1;
           H2=H2+U;
           if (H2>H)
              break;
           }
        }
    
    fprintf(o,"%i\n",sum);
    
    fclose(f);
    fclose(o);
    
    return 0;
}