Cod sursa(job #435813)

Utilizator lavinia.bBobonete Lavinia lavinia.b Data 7 aprilie 2010 21:23:49
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 4.1 kb
#include<stdio.h>
#include<stdlib.h>
void afisare(int g[2][100000],int N)
{
    int i,j;
    for(i=0;i<2;i++)
    {
        printf("\n");
        for(j=0;j<N;j++)
            printf("%d ",g[i][j]);
    }
}
/*void insert(int elem,int heap[],int N)
{
    if(count==N-1)
        return;
    ++count;
    int i=count;
    while(i>0 && heap[i/2]>elem)///i>1
    {
        heap[i]=heap[i/2];
        i/=2;
        heap[i]=elem;
    }
}
void delMin(int heap[],int N)
{
    if(count==0)
        return ;
    int last=heap[count];
    --count;
    int i=1;
    while(2*i < (count+1))
    {
        int child =2*i;
        if(((child+1) < (count+1)) && (heap[child+1]<heap[child]))
            child+=1;
            if(last<=heap[child])
                break;
            heap[i]=heap[child];
            i=child;
    }
    heap[i]=last;
}
*/


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);
		}


int findMin(int heap[],int size)
{
    return heap[1];
}

void ins(int elem,int heap[100000],int size)
{
    int i;
    for (i = ++size; heap[ i / 2 ] > elem; i /= 2)
        heap[ i ] = heap[ i / 2 ];
    heap[ i ] = elem;
}
void del(int heap[100000],int size)
{
    int i, Child;
    int LastElement=heap[ size--];

    for (i = 1; i * 2 <=size; i = Child) {
    Child = i * 2;
    if ((Child !=size) && (heap[ Child + 1 ]< heap[ Child ]))
            Child++;
    if (LastElement > heap[ Child ])
        heap[ i ] = heap[ Child ];
    else
        break;
    }
    heap[ i ] = LastElement;
}
void afisareheap(int heap[100000],int N)
{
    int i;
    printf("\n");
    for(i=0;i<N;i++)
        printf("%d ",heap[i]);
    printf("\n");
}

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);
		//printf("N=%d H=%d U=%d\n\n",N,H,U);
		ch=H;
        for(i=0;i<N;i++)
            fscanf(in,"%d %d",&g[0][i],&g[1][i]);


       // printf("\nMatricea initiala:\n");
       // afisare(g,N);
       // printf("\n\nSortata:\n");
        quickSort(g,0,N-1);
       // afisare(g,N);


        heap[1]=g[1][0];
        ch=ch-U;
        size=1;
        //printf("\nAm inserat %d .\n",g[1][0]);
        //afisareheap(heap,size+1);
        for(i=1;i<N;i++)
        {
            //printf("\nch=%d, g[0][%d]=%d \n",ch,i,g[0][i]);
            if(g[0][i]>ch)
            {
                //printf("\nMin:%d\n",findMin(heap,size));
                if(g[1][i]>findMin(heap,size))
                {
                    //printf("\nAm sters %d si am inserat in locul lui %d.\n",findMin(heap,size),g[1][i]);
                    del(heap,size);
                    size--;
                    ins(g[1][i],heap,size);
                    size++;
                    //afisareheap(heap,size+1);
                }
            }
            else
            {
               // printf("\nAm inserat %d .\n",g[1][i]);
                ins(g[1][i],heap,size);
                size++;
                ch=ch-U;
                //afisareheap(heap,size+1);
            }
        }
        int suma=0;
        for(i=1;i<size+1;i++)
            suma+=heap[i];
       // printf("\n\nSuma: %d \n\n",suma);
        fprintf(out,"%d",suma);

        fclose(in);
        fclose(out);
        return 0;
	}