Overview

In an \(N\)-day inventory inspection, given the maximum number of books that can be inspected each day \(L_i\) and the required number of inspections for each book \(R_j\), the problem asks to determine whether an inspection schedule satisfying all conditions simultaneously can be created. This problem can be efficiently solved by applying the idea of the “Gale-Ryser theorem,” which concerns the existence conditions of \((0,1)\) matrices.

Analysis

This problem can be reformulated as: “Does there exist an \(N \times M\) \((0,1)\) matrix where the row sums are at most \(L_i\) and the column sums are at least \(R_j\)?” Here, the constraint that the same book cannot be inspected more than once on the same day corresponds to each matrix element being \(0\) or \(1\) (i.e., the same element cannot be \(2\) or more).

Key Insight

When selecting the \(k\) books with the highest required inspection counts, the total number of inspections needed for those books is \(\sum_{j=1}^k R_j\). On the other hand, the maximum number of these \(k\) books that can be inspected on day \(i\) is the smaller of the following two limits: 1. The inspection capacity for that day: \(L_i\) 2. The number of selected book types: \(k\) (since each book can only be inspected once per day)

Therefore, the number of slots day \(i\) can provide for these \(k\) books is \(\min(k, L_i)\). For all \(k\) (\(1 \leq k \leq M\)), if the following condition is satisfied, it is possible to meet the inspection requirements: $\(\sum_{j=1}^k R_j \leq \sum_{i=1}^N \min(k, L_i)\)$

If for some \(k\) the left side (demand) exceeds the right side (supply limit), then no matter how the schedule is arranged, the conditions cannot be met.

Algorithm

To perform the determination efficiently, we process as follows:

1. Sorting:
   • Sort the required counts \(R\) in descending order (to take cumulative sums starting from the strictest conditions).
   • Sort the daily limits \(L\) in ascending order (to efficiently compute \(\min(k, L_i)\)).
2. Preparing prefix sums:
   • Precompute the prefix sums of \(L\).
3. Determination loop:
   • For \(k = 1\) to \(M\), compare \(\sum_{j=1}^k R_j\) with \(\sum_{i=1}^N \min(k, L_i)\).
   • The right side \(\sum \min(k, L_i)\) can be split into the sum of \(L_i\) for days where \(L_i < k\) and the sum of \(k\) for days where \(L_i \geq k\). Since \(L\) is sorted, the “boundary where \(L_i < k\)” can be found quickly using binary search or pointer advancement.

Complexity

• Time complexity: \(O(N \log N + M \log M)\)
  • Sorting \(L\) and \(R\) takes \(O(N \log N + M \log M)\).
  • The determination loop runs \(M\) times, and the boundary search (pointer movement) within it takes \(O(N + M)\) in total.
• Space complexity: \(O(N + M)\)
  • Used for storing arrays \(L, R\) and the prefix sums.

Implementation Notes

• Fast computation of \(\min(k, L_i)\): Scanning all \(N\) days inside every iteration of the loop would result in \(O(NM)\), which is too slow. By sorting \(L\) in ascending order and letting idx be the index of the “range where \(L_i\) is less than \(k\),” the right side can be computed in \(O(1)\) as (prefix sum of L up to idx) + (N - idx) * k.

• Large input: Since \(N, M\) can be as large as \(2 \times 10^5\), in Python it is advisable to read input quickly using methods such as sys.stdin.read().split().

  Source Code

import sys

# 競技プログラミングのエキスパートとして、効率的なアルゴリズムを用いて
# この問題を解決します。この問題は、各本を「少なくとも R_j 回」点検し、
# 各日に「最大 L_i 冊」点検するという制約のもとで、点検が可能かどうかを
# 判定するものです。これは、(0,1)行列の存在条件に関するゲイル＝ライザーの定理
# (Gale-Ryser theorem) の考え方を応用することで、効率的に解くことができます。

def solve():
    # 標準入力からすべてのデータを一度に読み込みます
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 日数, M: 本の冊数
    N = int(input_data[0])
    M = int(input_data[1])
    
    # L: 各日に点検可能な最大冊数, R: 各本に必要な最小点検回数
    L = list(map(int, input_data[2:2+N]))
    R = list(map(int, input_data[2+N:2+N+M]))
    
    # 判定条件を効率的にチェックするために、Rを降順、Lを昇順にソートします。
    # Rを降順にするのは、必要回数が多い本から順に累積和をとるためです。
    R.sort(reverse=True)
    L.sort()
    
    # Lの累積和を計算しておきます。これにより、任意のkに対して
    # sum_{i=1}^N min(k, L_i) を O(1) または O(log N) で計算可能になります。
    L_pref = [0] * (N + 1)
    current_L_sum = 0
    for i in range(N):
        current_L_sum += L[i]
        L_pref[i+1] = current_L_sum
        
    # 判定条件: すべての k (1 <= k <= M) について、
    # 必要な点検回数の上位 k 冊の合計が、それら k 冊に対して全日程で提供可能な
    # 最大枠数を超えていないかを確認します。
    # 式: sum_{j=1}^k R_j <= sum_{i=1}^N min(k, L_i)
    
    idx = 0
    R_sum_k = 0
    for k in range(1, M + 1):
        # Rの累積和（上位 k 冊の合計）
        R_sum_k += R[k-1]
        
        # L[idx] が k 未満である間、idxをインクリメントします。
        # k はループごとに1ずつ増加するため、idxは単調増加します。
        while idx < N and L[idx] < k:
            idx += 1
        
        # sum_{i=1}^N min(k, L_i) の計算:
        # 1. L_i < k の場合、min(k, L_i) = L_i (累積和 L_pref[idx] を使用)
        # 2. L_i >= k の場合、min(k, L_i) = k (残りの (N - idx) 日分)
        current_max_capacity = L_pref[idx] + (N - idx) * k
        
        # もし必要回数が供給可能な枠数を超えたら、達成不可能
        if R_sum_k > current_max_capacity:
            print("No")
            return

    # すべての k について条件を満たせば達成可能
    print("Yes")

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.