NTHU Online Judge #10925 (AC)

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

void Down_Heap(int [], int, int, int);
void Construct_by_Adjust(int [], int, int);
void Heap_Sort(int [], int, int);
int length; /* 0 < length < 10000 */

main(){
    int index, index2;
    int nodeAmount;
    int answer;
    int tempMax;
    float total_time = 0;
    clock_t start_time, end_time;

    FILE *fptr;
    fptr = fopen("D:\\PB.in.txt", "r");
    if (fptr==NULL) return EXIT_FAILURE;

    start_time = clock(); /* microsecond */
    while ( fscanf(fptr, "%d", &length)!=EOF ){
        int *arr1 = malloc(length * sizeof(int));
        int *arr2 = malloc(length * sizeof(int));
        int *sum  = malloc(length * length * sizeof(int));

        for ( index=0 ; index<length ; index++ )
            fscanf(fptr, "%d", &arr1[index]);
        for ( index=0 ; index<length ; index++ )
            fscanf(fptr, "%d", &arr2[index]);

        Heap_Sort( arr1, length, 1 );
        Heap_Sort( arr2, length, 1 );

        for ( index=0, nodeAmount=0 ; index<length ; index++ ){
            for ( index2=0 ; index2<length ; index2++ ){

                if ( index==0 ){
                    sum[nodeAmount++] = arr1[index] + arr2[index2];
                    continue;
                }

                if ( arr1[index]+arr2[index2] < tempMax )
                    sum[nodeAmount++] = arr1[index] + arr2[index2];
                    else break;

            } /* END index2 for */
            tempMax = sum[length-1];
        } /* END index for */

        Heap_Sort( sum, nodeAmount, 2 );

        for ( index=nodeAmount-1, answer=0 ; index>=nodeAmount-length ; index-- )
            answer += sum[index];
        printf("%d\n", answer);

        free(arr1); free(arr2);
        break;
    } /* END while */

    end_time = clock();
    total_time = (float)(end_time - start_time)/CLOCKS_PER_SEC;
    printf("elapsed time: %.3f sec \n", total_time);

    fclose(fptr);
    system("PAUSE");
    return EXIT_SUCCESS;
} /* END main() */

/* move arr[index] to the button to meets the property of heap */
void Down_Heap ( int arr[], int nodeAmount, int index, int mode ){
    int son;
    int up = arr[index];

    /* when arr[index] have son */
    while ( index < nodeAmount/2 ){
        son = 2*index + 1;  /* assume Left son is MAX(min) son */

        /* Max heap */
        if ( mode==1 ){
            if ( son+1 < nodeAmount && arr[son]<arr[son+1] )
                son++;            /* right son is MAX son */

            if ( up >= arr[son] ) /* arr[index] larger than MAX son */
                break;
        }

        /* min heap */
        else if ( mode==2 ){
            if ( son+1 < nodeAmount && arr[son]>arr[son+1] )
                son++;            /* right son is min son */

            if ( up <= arr[son] ) /* arr[index] less than min son */
                break;
        }

        /* else if arr[index] < arr[son] ( arr[index] > arr[son] ) */
        arr[index] = arr[son];
        index = son;
    } /* END while */
    arr[index] = up;
} /* END Down_Heap */

void Construct_by_Adjust ( int arr[], int nodeAmount, int mode ){
    int index;

    if ( mode==1 )      /* build Max heap */
        for ( index = nodeAmount/2 - 1 ; index >= 0 ; index-- )
            Down_Heap( arr, nodeAmount, index, 1 );

    else if ( mode==2 ) /* build min heap */
        for ( index = nodeAmount/2 - 1 ; index >= 0 ; index-- )
            Down_Heap( arr, nodeAmount, index, 2 );

} /* END Construct_by_Adjust() */

void Heap_Sort ( int arr[], int nodeAmount, int mode ){
    int temp;
    int round = 0;

    if ( mode==1 ) Construct_by_Adjust( arr, nodeAmount, 1 );
    else if ( mode==2 ) Construct_by_Adjust( arr, nodeAmount, 2 );

    while ( nodeAmount > 1 ){
        /* switch the first element and the least element */
        temp = arr[nodeAmount-1];
        arr[nodeAmount-1] = arr[0];
        arr[0] = temp;

        nodeAmount--;
        round++;

        if ( mode==1 )
            Down_Heap( arr, nodeAmount, 0, 1 );
        else if ( mode==2 ){
            Down_Heap( arr, nodeAmount, 0, 2 );
            if ( round==length ) break;
        }
    }
} /* END Heap_Sort() */