2928.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Problem Id:2928  User Id:fzk 
Memory:1620K  Time:248MS
Language:C++  Result:Accepted

Source 

#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( "Impossible\n" );
		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: %I64d\n", min*c, max*C );
	return 0;
}