Poj Solution 2928

http://poj.org/problem?id=2928

#include <algorithm>
#include <cstdio>
#include <vector>
#include <map>
#include <stack>
#include <memory.h>
#include <math.h>
using namespace std;

__int64 x[100010], y[100010];

int main( ) {
    int n, m, c, C, i, j;

    scanf( "%d%d%d%d", &n, &m, &c, &C );
    
    for( i=0; i<n; i++ )
        scanf( "%I64d", x+i );
    for( j=0; j<m; j++ )
        scanf( "%I64d", y+j );
    
    sort( x, x+n );
    sort( y, y+m );

    if( x[n-1] != y[m-1] ) {
        printf( "Impossiblen" );
        return 0;
    }
    
    __int64 min = 0, max = 0;
    x[n] = y[m] = x[n-1]+1;
        
    i=0, j=0;
    while( 1 ) {
        if( x[i] < y[j] ) {
            min += x[i];
            max += x[i]*(m-j);
            i++;
        }
        else if(x[i] == y[j] ) {
            min += x[i];
            max += x[i]*(n-i+m-j-1);
            i++, j++;
        }
        else {
            min += y[j];
            max += y[j]*(n-i);
            j++;
        }
        
        if( i >= n && j >= m )
            break;
        
    }
                
    printf( "Minimum: %I64d, maximum: %I64dn", min*c, max*C );
    return 0;
}



											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *