Observations

The answer does not change by sorting \(A\) in ascending order to satisfy \(A_1 \leq A_2 \leq \cdots A_N\), so we assume this.

Suppose we will give \(x_i\) large candies to child \(i\). Here, \(0 \leq x_i \leq A_i\) must hold.

The constraint that children \(1\) and \(k\)’s candies have the same total weight can be written as

\[(A_1 - x_1) X + x_1 Y = (A_k - x_k) X + x_k Y,\]

which can be deformed into

\[x_k = x_1 - \frac{(A_k - A_1)X}{Y-X}.\]

In other words, \(x_1 - x_k\) should take a constant value \(\displaystyle \frac{(A_k - A_1)X}{Y-X}\). Let \(D_k\) be this value. Since \(A_1 \leq A_k\), we have \(D_k \geq 0\).

For each \(k\), we have the following necessary conditions:

• Since \(x_1, x_2, \dots, x_N\) are integers, their differences \(D_k\) must be integers too.
• Since \(x_k \geq 0\) and \(x_1 \leq A_1\), the values \(D_k\) must be not greater than \(A_1\).

Conversely, if these conditions are satisfied, then letting \(x_k = A_1 - D_k\) satisfies the condition in the problem statement. Since \(x_k = x_1 - D_k\) and \(x_1 \leq A_1\), this is the maximum possible \(x_k\), so the answer is their sum.

Sample code (C++)

\(\displaystyle x_k = A_1 - \frac{(A_k - A_1)X}{Y-X}\) can be represented as \(\displaystyle x_k = A_k - \frac{(A_k - A_1)Y}{Y-X}\), so we adopt this expression in the following sample code.

#include <iostream>
using std::cin;
using std::cout;
using std::min;
using std::max;
#include <vector>
using std::vector;

typedef long long int ll;

ll n, x, y;
vector<ll> a;

ll solve () {
	ll mina = a[0];
	for (ll i = 0; i < n; i++) {
		mina = min(mina, a[i]);
	}

	ll sum = 0;
	ll w = mina * y;
	for (ll i = 0; i < n; i++) {
		ll vs = (a[i] - mina) * y;
		ll vt = (y - x);
		if (vs % vt != 0) {
			return -1;
		}
		ll minor = vs / vt;
		if (minor > a[i]) {
			return -1;
		}
		sum += (a[i] - minor);
	}

	return sum;
}

int main (void) {
	// input
	cin >> n >> x >> y;
	a.resize(n);
	for (ll i = 0; i < n; i++) {
		cin >> a[i];
	}

	ll ans = solve();
	cout << ans << "\n";
	

	return 0;
}