Cod sursa(job #441028)

Utilizator p1tagoraCalin Pelcea p1tagora Data 12 aprilie 2010 18:46:28
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2.94 kb
#include<stdlib.h>
#include<stdio.h>
#include<queue>
using namespace std;

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);      //citesc N,H,U
    fscanf(f,"%li",&U);
    
    long i=0,g,h;
    long v[2][100000];
    
    priority_queue< long,vector<long>,greater<long> > sol;    //sol e un heap care are primul element minim, si multimea de solutii partiale
        
    while (fscanf(f,"%li%li",&h,&g)!=EOF)   //pe prima linie din v pun inaltimile, pe a 2-a linie pun greutatile
          {
          v[0][i]=h;
          v[1][i]=g;
          i++;
          }
    quicksort(v,0,N-1);                     //sortez vectorul dupa inaltime, descrescator
    

    long H2=H;
    for (i=0;i<N;i++)                       //parcurg de la cele mai inalte in jos
        {
        if (v[0][i]<=H2)                    //daca ajung la ea
           {
           sol.push(v[1][i]);               //o pun in multimea de solutii partiale
           H2=H2-U;                         //scad inaltimea
           }
        else                                
            if (sol.top()<v[1][i])          //daca nu mai ajung la ea si e mai grea decat cea mai mica gutuie din sol
                   {                        
                   sol.pop();               //scot gutuia mai mica
                   sol.push(v[1][i]);       //si o pun pe cea noua
                   }
        }
    long sum=0;    
    while(!sol.empty())
        {
        sum=sum+sol.top();                  //calculez suma greutatilor gutuilor din multimea solutiilor partiale
        sol.pop();
        }
    
    fprintf(o,"%li\n",sum);
    
    fclose(f);
    fclose(o);
    
    return 0;
}