題意を再掲します。

• \(N\) 種類の材料から \(2\) 種類の料理を整数人分ずつ作る。料理 A を \(x\) 人分、料理 B を \(y\) 人分作るには、材料 \(i\) が \(A_i x + B_i y\) グラム必要で、この材料は \(Q_i\) グラムしかない。\(x + y\) がとりうる最大値を求めよ。
• 主な制約
  • \(N \leq 10\)
  • \(Q_i \leq 10^6\)

2 秒でできること

まず、材料の量の制約から、\(x\) も \(y\) も \(10^6\) 以下です（上では省きましたが、料理 \(1\) 人分を作るには何らかの材料が \(1\) グラムは必要です）。もし無限に時間があれば、\((x, y) = (0, 0), (0, 1), \dots, (0, 10^6), (1, 0), (1, 1), \dots, (10^6, 10^6)\) という \(10^{12}\) 個程度の可能性をすべて試せば十分です。しかし、\(2\) 秒では間に合いません。

（\(N = 10\) のときに \(N \times 10^{12} = 10^{13}\) 回、あるいはこの数倍程度の演算が必要です。仮に \(10^{13}\) 回でよいとしても、この解説の執筆に使っているパソコンのプロセッサの周波数は \(2.40 \times 10^9\) Hz で、\(10^{13} / (2.40 \times 10^9) \fallingdotseq 4000\) 秒ほどかかります。）

そこで、\(x\) のみについて \(x = 0, 1, \dots, 10^6\) のすべての可能性を検討することにします。目的は \(x+y\) の最大化であるため、\(x\) を固定した際に \(y\) がとりうる最大値がわかれば十分です。

片方を固定して

\(x\) の値を \(0, 1, \dots, 10^6\) のいずれかに固定します。材料 \(i\) の量について、\(A_i x + B_i y \leq Q_i\)、あるいは \(B_i y \leq Q_i - A_i x\) が成り立つ必要があります。

まず、\(Q_i - A_i x < 0\) であるような材料 \(i\) がひとつでもあれば、そもそも \(x\) 人分の料理 A を作れず、この \(x\) は棄却します。以下、すべての \(i\) に対して \(Q_i - A_i x \geq 0\) であるとします。

\(B_i = 0\) なら、料理 B を何人分作っても材料 \(i\) は不足しません。そうでないなら、料理 B を作るのが \(\lfloor (Q_i - A_i x) / B_i \rfloor\) 人分までなら材料 \(i\) は不足しません（\(\lfloor z \rfloor\) は \(z\) の小数点以下を切り捨てたもの）。この計算をすべての材料 \(i\) に対して行えば、このような上限のうち最小のものが \(y\) の最大値となります。これと \(x\) との和が答えの候補です。

この処理を \(x = 0, 1, \dots, 10^6\)（あるいは \(\max(Q_i)\) まで）のすべてに対して行い、答えの候補のうち最大のものを答えれば \(O(N \max(Q_i))\) 時間で問題を解けます。

なお、\(x\) や \(y\) が整数という条件がなければこの問題は線型計画問題と呼ばれますが、この条件が重大な障害となります。

実装例（Python）

N = int(input())
Q = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
INF = 10**18

ans = 0
for x in range(max(Q) + 1):
    y = INF
    for i in range(N):
        if Q[i] < A[i] * x:
            y = -INF
        elif B[i] > 0:
            y = min(y, (Q[i] - A[i] * x) // B[i])
    ans = max(ans, x + y)
print(ans)