Let’s restate the problem.

• You want to make two types of dishes in integer servings using \(N\) kinds of ingredients. To make \(x\) servings of dish A and \(y\) servings of dish B, you need \(A_i x + B_i y\) grams of ingredient \(i\), and you only have \(Q_i\) grams of this ingredient. Find the maximum possible value of \(x + y\).
• Main constraints:
  • \(N \leq 10\)
  • \(Q_i \leq 10^6\)

What can be done in two seconds

First, due to the constraints on the amounts of ingredients, both \(x\) and \(y\) must be at most \(10^6\) (although not mentioned above, at least one gram of some ingredient is necessary to make one serving of a dish). If we had infinite time, we could try all the approximately \(10^{12}\) possibilities that are \((x, y) = (0, 0), (0, 1), \dots, (0, 10^6), (1, 0), (1, 1), \dots, (10^6, 10^6)\). However, this is not feasible in two seconds.

(When \(N = 10\), we would need \(N \times 10^{12} = 10^{13}\) operations, or perhaps several times this number. Even if \(10^{13}\) operations were sufficient, the processor frequency of the computer used to write this editorial is \(2.40 \times 10^9\) Hz, so it would take approximately \(10^{13} / (2.40 \times 10^9) \fallingdotseq 4000\) seconds.)

Therefore, we will only consider all possibilities for \(x\) that are \(x = 0, 1, \dots, 10^6\). Since our goal is to maximize \(x+y\), it is sufficient to know the maximum possible value of \(y\) when \(x\) is fixed.

Fixing one side

We fix the value of \(x\) to one of \(0, 1, \dots, 10^6\). For ingredient \(i\), it is necessary that \(A_i x + B_i y \leq Q_i\), or \(B_i y \leq Q_i - A_i x\).

First, if there is any ingredient \(i\) such that \(Q_i - A_i x < 0\), then we cannot make \(x\) servings of dish A in the first place, so we reject this value of \(x\). From now on, we assume that \(Q_i - A_i x \geq 0\) for all \(i\).

If \(B_i = 0\), then we can make any number of servings of dish B without running out of ingredient \(i\). Otherwise, we can make up to \(\lfloor (Q_i - A_i x) / B_i \rfloor\) servings of dish B without running out of ingredient \(i\) (where \(\lfloor z \rfloor\) is \(z\) rounded down to the nearest integer). If we perform this calculation for all ingredients \(i\), the smallest of these upper limits will be the maximum value of \(y\). The sum of this and \(x\) is a candidate for the answer.

We perform this process for all \(x = 0, 1, \dots, 10^6\) (or up to \(\max(Q_i)\)), and report the largest of the answer candidates to solve the problem in \(O(N \max(Q_i))\) time.

Incidentally, if \(x\) and \(y\) were not required to be integers, this problem would be called a linear program, but this condition poses a significant obstacle.

Sample implementation (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)