Overview

This problem asks us to find the maximum number of days Takahashi can operate his food stall while paying daily wages to part-time workers within his budget of \(S\) yen. However, if the result of subtracting daily wages from each day’s sales becomes negative, his funds may run out.

Analysis

In this problem, each day of operation earns sales of \(\sum A_i\) and pays total daily wages of \(\sum B_j\) to all part-time workers. Therefore, the daily profit/loss is:

\[ \text{profit\_per\_day} = \sum_{i=1}^{N} A_i - \sum_{j=1}^{M} B_j \]

Key Observations

• If \(\text{profit\_per\_day} \geq 0\), the sales are greater than or equal to the expenses, so the stall can operate indefinitely. In this case, output -1.
• Otherwise (\(\text{profit\_per\_day} < 0\)), the funds decrease day by day. We need to find the maximum number of days before the funds drop below 0.

Change in Funds

After operating for \(d\) days, the remaining funds can be expressed as:

\[ \text{money} = S + d \cdot \text{profit\_per\_day} \]

Since sales are received and then wages are paid each day, we need to ensure funds don’t become negative midway. However, when \(\text{profit\_per\_day}\) is negative, funds decrease each day, so the first time they drop below 0 will be on the last day.

Therefore, the condition is simply:

\[ S + d \cdot \text{profit\_per\_day} \geq 0 \]

We need to find the maximum integer \(d\) that satisfies this inequality.

Why Binary Search?

Since the upper bound of \(d\) can be extremely large (up to \(10^{18}\)), a linear search would be too slow. Therefore, we use binary search to efficiently find the maximum \(d\) that satisfies the condition.

Algorithm

1. Compute the total popularity of all items \(\sum A_i\) and the total daily wages \(\sum B_j\).
2. Calculate \(\text{profit\_per\_day} = \sum A_i - \sum B_j\).
3. If \(\text{profit\_per\_day} \geq 0\), output -1 and terminate.
4. Otherwise, use binary search to find the “maximum number of days where funds remain non-negative.”
   • Search range: \(0 \leq d \leq 10^{18}\)
   • Condition: \(S + d \cdot \text{profit\_per\_day} \geq 0\)

Complexity

• Time complexity: \(O(N + M + \log(10^{18}))\)
  • \(O(N + M)\) for computing the sums, \(O(\log(10^{18}))\) for the binary search
• Space complexity: \(O(N + M)\)
  • For storing the input data in lists

Implementation Notes

• Use sys.stdin.read instead of input() for fast input processing (to handle large inputs).

• There is no need to worry about integer overflow in division or comparisons, but pay attention to the sign (since profit_per_day is negative).

• The binary search termination condition is left <= right, updating left or right based on the evaluation of mid.

  Source Code

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    S = int(data[2])
    
    A = list(map(int, data[3:3+N]))
    B = list(map(int, data[3+N:3+N+M]))
    
    total_revenue = sum(A)
    total_cost = sum(B)
    
    if total_revenue >= total_cost:
        print(-1)
        return
    
    # 一日あたりの利益（実際はマイナス）
    profit_per_day = total_revenue - total_cost
    
    # 最大日数を二分探索で求める
    # 所持金が0以上である最大の日数dについて探す
    # d日営業した後の所持金 = S + d * profit_per_day
    # ただし、毎日日給を支払う前に売上有を得るため、制約は
    # S + k * profit_per_day >= 0 for all k in 1 to d
    # すなわち、min(S + k * profit_per_day) >= 0 for k=1..d
    # この最小値はk=dのとき最小（profit_per_day < 0なので）
    # よって、S + d * profit_per_day >= 0
    # d <= ( -S ) / profit_per_day （profit_per_day < 0 なので不等号逆）
    # 実際にdが整数なので、floor( (-S) / profit_per_day )
    # ただし、profit_per_day が負の整数なので、
    # d = floor( (-S) / profit_per_day ) = ( -S - profit_per_day + 1 ) // profit_per_day
    # ではなく、単純に(S // (-profit_per_day))で良いかもしれないが注意
    
    # 安全に二分探索で求める
    left = 0
    right = 10**18
    answer = 0
    
    while left <= right:
        mid = (left + right) // 2
        # mid日間営業した後の所持金
        money = S + mid * profit_per_day
        if money >= 0:
            answer = mid
            left = mid + 1
        else:
            right = mid - 1
            
    print(answer)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.