以下のような 問題A と 問題B を考えます。

問題A

\(N\) 個の料理を好きな順で並べ、その順で食べていく。ただし、食べた料理の甘さの合計が \(X\) より大きくなるとその時点で食べるのをやめる。食べる料理の個数の最小値はいくつか？

問題B

\(N\) 個の料理を好きな順で並べ、その順で食べていく。ただし、食べた料理のしょっぱさの合計が \(Y\) より大きくなるとその時点で食べるのをやめる。食べる料理の個数の最小値はいくつか？

料理の並べ方を固定すると、元の問題で食べるのをやめる条件を満たしているとき 問題A と 問題B のどちらかで食べるのをやめる条件を満たし、問題A と 問題B のどちらかで食べるのをやめる条件を満たしているとき元の問題でも食べるのをやめる条件を満たしています。

前者の事実から \(\min\) (問題A の答え, 問題Bの答え) \(\leq\) (本問題の答え) が従い、後者の事実から (本問題の答え) \(\leq\) (問題A の答え) と (本問題の答え) \(\leq\) (問題B の答え)が従うので、本問題の答えは 問題A と 問題B の最小値に等しいです。

したがって 問題A と 問題B が解ければよいですが、これはそれぞれ \(A_i\) と \(B_i\) の降順にソートして順に食べていくことが最小値を達成するために最適な行動の一つとなります。

実装例

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
	ll n, x, y;
	cin >> n >> x >> y;
	vector<ll> a(n), b(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < n; i++) cin >> b[i];
	sort(a.begin(), a.end(), greater<>());
	sort(b.begin(), b.end(), greater<>());
	int c1 = 0, c2 = 0;
	ll sx = 0, sy = 0;
	for (int i = 0; i < n; i++) {
		sx += a[i];
		c1++;
		if (sx > x) break;
	}
	for (int i = 0; i < n; i++) {
		sy += b[i];
		c2++;
		if (sy > y) break;
	}
	cout << min(c1, c2) << '\n';
}