Overview

This problem asks you to compute the daily balance (revenue − total wages) of a food stall, then determine whether it results in a profit or loss. If there is a loss, calculate the maximum number of days the stall can operate before running out of money.

Analysis

First, let’s organize how the available funds change with each day of operation.

• Daily revenue: The sum of popularity of all products \(\displaystyle\sum_{i=1}^{N} A_i\)
• Daily expenses: The sum of daily wages for all part-time workers \(\displaystyle\sum_{j=1}^{M} B_j\)
• Daily balance (profit): \(P = \displaystyle\sum_{i=1}^{N} A_i - \sum_{j=1}^{M} B_j\)

After operating for \(d\) days, the remaining funds are:

\[S + d \times P\]

Case Analysis

Case 1: When \(P \geq 0\) (profit is zero or positive)

Since the funds do not decrease with each day of operation (they either increase or stay the same), the stall can operate indefinitely. The answer is -1.

Case 2: When \(P < 0\) (daily loss)

The funds decrease by \(|P|\) yen each day. The condition for the funds to remain \(0\) or more after \(d\) days is:

\[S + d \times P \geq 0\]

\[S - d \times |P| \geq 0\]

\[d \leq \frac{S}{|P|}\]

Since \(d\) is an integer, the maximum number of days is \(\left\lfloor \dfrac{S}{|P|} \right\rfloor\).

Concrete Example

For example, when \(N=2, M=2, S=10, A=[3, 5], B=[4, 6]\):

• Total revenue \(= 3 + 5 = 8\)
• Total wages \(= 4 + 6 = 10\)
• Daily loss \(= 10 - 8 = 2\) yen

Maximum number of days \(= \lfloor 10 / 2 \rfloor = 5\) days. Verifying: after 5 days, the remaining funds are \(10 + 5 \times (-2) = 0\) yen, which is exactly \(0\) yen, so it’s OK.

Algorithm

1. Compute the sum of array \(A\) (revenue) and the sum of array \(B\) (wages).
2. Calculate the daily profit \(P = (\text{revenue}) - (\text{wages})\).
3. If \(P \geq 0\), output -1.
4. If \(P < 0\), output \(\left\lfloor S / |P| \right\rfloor\).

Complexity

• Time complexity: \(O(N + M)\) (just computing the sums of the arrays)
• Space complexity: \(O(N + M)\) (storing the input)

Implementation Notes

• The upper bound for \(S\) is \(10^{18}\), and the upper bound for \(A_i, B_j\) is \(10^9\), with up to \(10^5\) elements each, so the sum can be at most around \(10^{14}\). Python handles arbitrary-precision integers, so there is no worry about overflow, but when implementing in C++ or similar languages, you need to use the long long type.

• When \(P = 0\) (revenue and wages are exactly equal), the funds do not decrease, so the stall can operate indefinitely and the output should be -1. Be careful not to overlook this case.

• Python’s integer division // truncates toward negative infinity, but since \(S \geq 0\) and \(|P| > 0\) here, it coincides with standard floor division, so there is no issue.

  Source Code

def main():
    import sys
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    S = int(input_data[idx]); idx += 1
    
    A = []
    for i in range(N):
        A.append(int(input_data[idx])); idx += 1
    B = []
    for i in range(M):
        B.append(int(input_data[idx])); idx += 1
    
    total_sales = sum(A)
    total_wages = sum(B)
    
    daily_profit = total_sales - total_wages
    
    if daily_profit >= 0:
        # Each day we gain or break even, so we can operate forever
        print(-1)
    else:
        # daily_profit < 0, so each day we lose (-daily_profit) yen
        # After d days: S + d * daily_profit >= 0
        # S + d * daily_profit >= 0
        # d <= S / (-daily_profit)
        loss_per_day = -daily_profit
        print(S // loss_per_day)

main()

---

This editorial was generated by claude4.6opus-thinking.