Hippo Circus (UVA 13054) by aizu_f
Contest: 3738    RunID: 20174056    Status: Accepted    Date: Sat Oct 14 15:08:48 JST 2017


#include <bits/stdc++.h>

using namespace std;

int compare(const void *a, const void *b){
	return (*(int *)a - *(int*)b);
}

int solve(int n, int h, int alone, int carry, int height[]){
	bool isCarryFaster = alone * 2 > carry;
	if(isCarryFaster){
		qsort(height, n, sizeof(int), compare);
		int i = 0, j = n - 1;
		int count = 0;
		while(i < j){
			if(height[i] + height[j] < h){
				count++;
				i++;
				j--;
			}else j--;
		}
		return count * carry + (n - 2 * count) * alone;
	}else{
		return alone * n;
	}
}

int main(){
	int t;
	cin >> t;
	int i = 1;
	while(t--){
		int N, H, a, d;
		cin >> N >> H >> a >> d;
		int height[N];
		for(int j = 0; j < N; ++j) cin >> height[j];

		cout << "Case " << i++ << ": " << solve(N, H, a, d, height) << endl;
	}
	return 0;
}