NTHU Online Judge #10925 (TLE)

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

void Down_Heap(int [], int, int);
void Construct_by_Adjust(int [], int);
void Heap_Sort(int [], int);

main(){
    int index, index2;
    int nodeAmount;
    int length;     /* 0 < length < 10000 */
    int answer;

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

    float total_time = 0;
    clock_t start_time, end_time;
    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]);

        for ( index=0, nodeAmount=0 ; index<length ; index++ )
            for ( index2=0 ; index2<length ; index2++ )
                sum[nodeAmount++] = arr1[index] + arr2[index2];

        Heap_Sort( sum, nodeAmount );

        for ( index=0, answer=0 ; index<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() */

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

    /* when arr[index] have son */
    while ( index < nodeAmount/2 ){
        son = 2*index + 1;  /* assume Left son is MAX son */
        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;

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

/* Max heap */
void Construct_by_Adjust ( int arr[], int nodeAmount ){
    int index;
    for ( index = nodeAmount/2 - 1 ; index >= 0 ; index-- )
        Down_Heap( arr, nodeAmount, index );
} /* END Construct_by_Adjust() */

void Heap_Sort ( int arr[], int nodeAmount ){
    int temp;
    Construct_by_Adjust( arr, nodeAmount ); /* construct heap */

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

        nodeAmount--;
        Down_Heap( arr, nodeAmount, 0 );
    }
} /* END Heap_Sort() */