Cod sursa(job #436272)

Utilizator lavinia.bBobonete Lavinia lavinia.b Data 8 aprilie 2010 13:51:53
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 3.06 kb

/*Bobonete Lavinia,325CA*/

#include<stdio.h>
#include<stdlib.h>

//functia de partitionare de la Quicksort
int partitionare(int mat[2][100000],int left,int right)
	{
		int i=left,j=right;
		int temp1,temp2;
		int pivot=mat[0][(left+right)/2];
		while(i<=j)
			{
				while(mat[0][i]>pivot)
					i++;
				while(mat[0][j]<pivot)
					j--;
				if (i<=j)
            		{
            			temp1 = mat[0][i];
            			mat[0][i]=mat[0][j];
            			mat[0][j]=temp1;
            			temp2 = mat[1][i];
            			mat[1][i]=mat[1][j];
            			mat[1][j]=temp2;
            			i++;
            			j--;
            		}
			}
			return i;
	}

void quickSort(int mat[2][100000],int left,int right)
		{
			int index = partitionare(mat, left, right);
			if(left<index-1)
				quickSort(mat,left,index-1);
			if (index<right)
				quickSort(mat,index,right);
		}


//elementul minim din heap; fiind un heap minim,primul element va fi cel mai mic
int findMin(int heap[100000],int size)
	{
    	return heap[1];
	}

//functia de inserare in heap
void ins(int elem,int heap[100000],int size)
	{
    	int i=size+1;
   	 	while(i>1 && heap[i/2]>elem)
    		{
        		heap[i]=heap[i/2];
    			i/=2;
    		}
    	heap[i]=elem;
	}

//functia de stergere din heap
void del(int heap[100000],int size)
	{
		int i,c,aux=heap[size];
		size=size-1;
    	for(i=1;i*2<=size;i=c)
   			{
    			c=i*2;
    			if((c!=size) && (heap[c+1]<heap[c]))
    				c++;
    			if(aux>heap[c])
    				heap[i]=heap[c];
    			else
        			break;
    		}
    	heap[i]=aux;
	}
	
int main()
	{
		FILE *in;
		FILE *out;
		in=fopen("gutui.in","r");
		out=fopen("gutui.out","w");
		int N,H,U;
		int i,g[2][100000];
		int heap[100000];
		int ch;
		int size;
		fscanf(in,"%d %d %d",&N,&H,&U);
		ch=H;//inaltimea maxima curenta la care poate ajunge Gigel
        for(i=0;i<N;i++)
            fscanf(in,"%d %d",&g[0][i],&g[1][i]);
        quickSort(g,0,N-1);
        
        heap[1]=g[1][0];
        ch=ch-U; //la fiecare gutuie pusa in heap,inaltimea la care Gigel poate ajunge va scadea cu U
        size=1; //marime heap
        for(i=1;i<N;i++)
        {
            if(g[0][i]>ch) //daca Gigel nu poate ajunge la gutuie
            {
                if(g[1][i]>findMin(heap,size)) //dar am gasit o gutuie cu greutate mai mare decat cea mai mica greutate pusa in heap,inlocuim greutatea minima cu cea noua
                {
                    del(heap,size);
                    size--;
                    ins(g[1][i],heap,size);
                    size++;
                }
            }
            else //daca Gigel poate ajunge la gutuie,inseram in heap greutatea gutuii
            {
                ins(g[1][i],heap,size);
                size++;
                ch=ch-U;
            }
        }
        
        int suma=0;
        for(i=1;i<size+1;i++)
            suma+=heap[i];//suma totala a greutatilor gutuilor puse in heap
            
        fprintf(out,"%d",suma);
        fclose(in);
        fclose(out);
        return 0;
	}