Overview

This is a problem of determining whether \(N\) items can all be loaded onto \(M\) trucks (each with a capacity limit). Since both the number of items and the number of trucks are at most 15, which is small, we can solve this efficiently using Bitmask DP.

Analysis

1. Difficulty of Naive Search

If we naively try assigning each item to a truck, there are up to \(M^N = 15^{15}\) combinations, which cannot be computed within the time limit. Moreover, the result may vary depending on the order in which items are loaded, so we need a clever approach.

2. Focusing on the Constraints

Notice that the number of items \(N\) is very small at 15. When the state of “whether each element has been used or not” is this small, Bitmask DP is effective.

By representing the set of items as one of \(2^N\) integers (bitmasks), we can manage the state of “which items have been loaded.”

3. Optimal State Definition

When loading a set of items represented by mask, it is better to leave as much “room” as possible, as this increases the possibility of loading the remaining items. Specifically, we update states with the following priorities: 1. Minimize the number of trucks used 2. If the number of trucks is the same, maximize the remaining capacity of the last truck being used

By sorting the trucks in decreasing order of capacity, we can pack items more efficiently.

Algorithm

Solution Using Bitmask DP

We prepare the following two arrays: - dp_k[mask]: The minimum truck index needed to load the set of items mask - dp_rem[mask]: The maximum remaining capacity of the last truck at that point

Procedure

1. Preprocessing:
   • Sort the truck capacities \(C\) in descending order (largest first).
   • If the total weight of all items exceeds the total capacity of all trucks, immediately output No.
2. Initialization:
   • dp_k[0] = 0 (if there are no items, use truck 0)
   • dp_rem[0] = C[0] (remaining capacity is the full capacity of truck 0)
   • Initialize all other values to unreachable states.
3. Transitions: For each mask, consider adding an item \(i\) that has not been loaded yet.
   • If it fits in the current truck: Load it as is and reduce the remaining capacity.
   • If loading onto the next truck: If the capacity \(C[k+1]\) of the next truck is at least as large as item \(i\), use a new truck to load it.
4. Judgment: In the state where all items are loaded, (1 << N) - 1, if the number of trucks used is at most \(M\), output Yes; otherwise, output No.

Complexity

• Time Complexity: \(O(N \cdot 2^N)\)
  • The number of states is \(2^N\), and the transitions from each state (choosing an item) are \(N\) possibilities. When \(N=15\), this is \(15 \times 2^{15} \approx 4.9 \times 10^5\), which comfortably fits within the time limit.
• Space Complexity: \(O(2^N)\)
  • This is the size of the arrays holding the bitmask states.

Implementation Notes

• Sorting trucks: By using trucks with larger capacity first, we increase the probability of fitting items and simplify the DP transitions.

• Early termination: By checking sum(W) > sum(C), we can eliminate obviously impossible cases.

• Bit operations: We use mask & (1 << i) to check whether item \(i\) has been used, and mask | (1 << i) to mark it as used. In the code, a pow2 array is precomputed for faster bit operations.

  Source Code

import sys

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])
    
    # 各荷物の重さと各トラックの積載制限を取得します
    W = list(map(int, input_data[2:2+N]))
    C = list(map(int, input_data[2+N:2+N+M]))
    
    # 荷物の重さの合計がトラックの積載制限の合計を超えている場合は不可能です
    if sum(W) > sum(C):
        print("No")
        return

    # トラックの積載制限を降順にソートします
    # 容量の大きいトラックから優先的に使うことで、すべての荷物を積み込める可能性を最大化します
    C.sort(reverse=True)
    
    # トラックの数が荷物の数より多い場合、最大でもN台のトラックしか必要ありません
    if M > N:
        C = C[:N]
        M = N
        
    # ビットDPを用いて、荷物の各集合（mask）を積み込むのに必要な最小のトラック数と、
    # その際に最後に使ったトラックの残り容量を管理します。
    # dp_k[mask]: maskで表される荷物の集合を積み込むのに必要な最小のトラックのインデックス (0からM-1)
    # dp_rem[mask]: その時の最後のトラックの最大残り容量
    dp_k = [M + 1] * (1 << N)
    dp_rem = [-1] * (1 << N)
    
    # 初期状態：荷物を一つも積んでいないとき、0番目のトラックを使用し、その残り容量はC[0]です
    dp_k[0] = 0
    dp_rem[0] = C[0]
    
    # ビット演算のための2の累乗を事前に計算しておきます
    pow2 = [1 << i for i in range(N)]
    
    # 全ての荷物の集合（ビットマスク）についてループします
    for mask in range(1 << N):
        k = dp_k[mask]
        rem = dp_rem[mask]
        
        # この状態が到達不可能な場合はスキップします
        if k >= M:
            continue
        
        # まだ積み込んでいない荷物 i を追加することを試みます
        for i in range(N):
            if not (mask & pow2[i]):
                new_mask = mask | pow2[i]
                wi = W[i]
                
                # 選択肢1: 現在のトラック k に荷物 i を積む
                if wi <= rem:
                    nk, nrem = k, rem - wi
                # 選択肢2: 次のトラック k+1 に荷物 i を積む
                elif k + 1 < M and wi <= C[k+1]:
                    nk, nrem = k + 1, C[k+1] - wi
                else:
                    # どちらのトラックにも積めない場合はスキップ
                    continue
                
                # dp[new_mask] を更新します（使用トラック数が少ない、またはトラック数が同じなら残り容量が多い方を優先）
                if nk < dp_k[new_mask]:
                    dp_k[new_mask] = nk
                    dp_rem[new_mask] = nrem
                elif nk == dp_k[new_mask] and nrem > dp_rem[new_mask]:
                    dp_rem[new_mask] = nrem
                        
    # すべての荷物を積み込んだ状態（(1 << N) - 1）が有効なトラック数で到達可能か判定します
    if dp_k[(1 << N) - 1] < M:
        print("Yes")
    else:
        print("No")

if __name__ == '__main__':
    solve()

---

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