pat 1037

1037.cpp

#include <cstdio>
#include <algorithm>

using namespace std;

void quicksort( int *num, int start, int end){
    if( start >= end ){
        return;
    }
    int temp = num[start];
    int i=start;
    int j=end;
    while(i<j){
        while( j>i && num[j] >= temp ){
            j--;
        }
        if( j>i){
            num[i++] = num[j];
        }
        if( i<j && num[i] <= temp ){
            i++;
        }
        if( i<j ){
            num[j--] = num[i];
        }
    }
    num[i] = temp;
    quicksort( num, start, i-1 );
    quicksort( num, i+1, end );
}

int main(){
    int m, n;
    scanf( "%d", &m );
    int *numc = (int *)malloc(sizeof(int)*m);
    int i;
    for( i=0; i<m; i++){
        scanf("%d", &numc[i] );
    }
    scanf("%d", &n );
    int *nump = (int *)malloc(sizeof(int)*n);
    for( i=0; i<n; i++){
        scanf("%d", &nump[i] );
    }
    /*
    quicksort( numc, 0, m-1 );
    quicksort( nump, 0, n-1 );
    */
    sort(numc, numc + m, greater<int>());
    sort(nump, nump + n, greater<int>());
    
    long int sum = 0;
    int upper = m < n ? m : n;
    for( i=0; i < upper && numc[i]>0 && nump[i]>0; i++){
        sum += numc[i]*nump[i];
    }
    for( i=1; i <= upper && numc[m-i] <0 && nump[n-i]<0; i++){
        sum += numc[m-i]*nump[n-i];
    }
    printf("%ld\n", sum );
    return 0;
}