Feasible combination

A combination of products \(A_{i_1}, \dots, A_{i_n}, B_{j_1}, \dots, B_{j_m}\) can be purchased if and only if:

• the total price, \(\displaystyle \sum_{1 \leq k \leq n} A_{i_k} + \sum_{1 \leq k \leq m} B_{j_k}\), is at most \(X+KY\), and
• the number of \(K\)-dollar bills required, \(\displaystyle \sum_{1 \leq k \leq m} \lceil B_{j_k} / K \rceil\), is at most \(Y\).

The necessity is obvious. We can assert that the combination can indeed be purchased by first buying all the \(m\) drinks, then buying all the \(n\) desserts.

Solution

Suppose we buy \(m\) products from \(B\). Then it is optimal to choose the \(m\) cheapest items. Likewise, it is optimal to choose from the cheaper ones from \(A\), too.

When the number of items taken from \(B\) is fixed, the amount of money remaining for \(A\) is determined, so one can obtain the number of items that can be taken from \(A\).

Therefore, by trying the number of items from \(B\) exhaustively, and binary searching for the number of items from \(A\), the answer can be found in \(O(N \log N)\) time.

Note that the less items we pick from \(B\), the more money we can spend for \(A\), so the process other than sorting can be done in \(O(N)\) time using the sliding window technique.

Bonus

Under the setting of this problem, we can prove that the following construction achieves the maximum value: inspect each product in ascending order of the item. Check if the combination is still purchasable when that item is added. Greedily add it to the combination when it is possible.

Sample code (C++)

#include <iostream>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
#include <vector>
using std::vector;
using std::pair;
#include <map>
using std::map;
using std::max;
using std::min;


#ifdef DEBUG
const int debug = 1;
#else
const int debug = 0;
#endif

using ll = int64_t;
using P = pair<ll, ll>;

const ll FOD = 998244353;
#include <atcoder/modint>
using mint = atcoder::modint998244353;
#include <atcoder/convolution>
using atcoder::convolution;

ll n, m, k;
ll x, y;
vector<ll> a, b;

inline void output (const ll x) {
	cout << x << "\n";
}

vector<ll> accum (const vector<ll> &a) {
	ll sz = (ll)a.size();
	vector<ll> b(sz+1, 0);
	b[0] = 0;
	for (ll i = 0; i < sz; i++) {
		b[i+1] = b[i] + a[i];
	}
	return b;
}

void solve() {
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());

	vector<ll> bk(m);
	for (ll i = 0; i < m; i++) {
		bk[i] = (b[i] - 1) / k + 1;
	}

	vector<ll> ac = accum(a);
	vector<ll> bc = accum(b);
	vector<ll> bkc = accum(bk);

	ll ans = 0;
	for (ll ri = 0; ri <= m; ri++) {
		ll s = (x+y*k) - bc[ri];
		ll sk = y - bkc[ri];
		if (s < 0 || sk < 0) break;

		ll li = ([&]() -> ll {
			ll ok = 0, ng = n+1;
			while (ok + 1 < ng) {
				ll med = (ok + ng) / 2;
				if (ac[med] <= s) {
					ok = med;
				} else {
					ng = med;
				}
			}
			return ok;
		})();

		ans = max(ans, li + ri);
	}

	output(ans);


	return;
}

int main (void) {
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);

	cin >> n >> m >> k;
	cin >> x >> y;
	a.resize(n);
	b.resize(m);
	for (ll i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (ll i = 0; i < m; i++) {
		cin >> b[i];
	}

	
	solve();

	return 0;
}