Overview

We determine whether \(N(\le 15)\) items can be assigned to \(M(\le 15)\) trucks with weight limits, where each item must be assigned to exactly one truck. This is solved using bitmask DP (subset DP).

Analysis

Key Observations

• Since \(N,M\le 15\), a DP approach managing “which items have already been loaded” using a bitmask (\(0\sim 2^N-1\)) is practical.
• For each truck, we need to select “a set of items to load.” This becomes a problem of selecting “a subset of the remaining items.”

Why the Naive Solution is Too Slow

If we enumerate all subsets of remaining items for each truck, the number of states is \(2^N\), and subset enumeration for each state is at most \(2^{N}\), leading to approximately \(O(M\cdot 3^N)\) in the worst case (a common pattern in subset DP). Even with \(N=15\), this can become heavy depending on the implementation.

How to Solve This (Optimization Techniques)

1. Early pruning of impossible cases
   • If \(\max_i W_i > \max_j C_j\), that item cannot fit in any truck, so output No immediately
   • If \(\sum_i W_i > \sum_j C_j\), total capacity is insufficient, so output No immediately
2. Reduce the number of trucks
   • At most \(N\) trucks will actually carry items, so when \(M>N\), it suffices to keep only the \(N\) trucks with largest capacities (smaller trucks are less useful).
3. Process trucks with smaller capacity first
   • Trucks with smaller capacity have limited subsets that can fit, so reachable states grow slowly, keeping the DP from exploding.
4. Switch enumeration methods based on the situation
   • Pre-compute a list fit_list of subsets that fit in the truck (subsets with weight sum \(\le cap\)), and use it for transitions
   • For a state mask, enumerate all subsets of the “remaining set rem”
   • Choose whichever method processes fewer subsets.

Algorithm

1. Preprocessing

• Let full = (1<<N)-1 represent “all items have been loaded.”
• Sort truck capacities \(C\) in descending order and keep only \(M=\min(M,N)\) trucks (prioritizing larger ones).
• Since we want to process smaller capacities first in the DP, sort the remaining \(C\) in ascending order.
• Precompute the weight sum sum_w[mask] for each subset mask.
  • Example: Take the lowest set bit lsb of mask, then sum_w[mask] = sum_w[mask ^ lsb] + W[i] can be computed in \(O(2^N)\).

2. DP Definition

• dp[mask] = True
  “It is possible to have loaded the item set mask (items corresponding to set bits) using the trucks processed so far”
• Initial state: dp[0]=True (nothing loaded yet)
• Maintain reachable as a “list of masks currently True” to avoid unnecessary full traversals.

3. Transitions (for each truck capacity cap)

• First, for each mask in reachable, compute rem = full ^ mask (remaining items), and
  • If sum_w[rem] <= cap, we can load all remaining items on this truck and finish, so output Yes immediately.
• Next, use subsets sub that can be loaded on this truck (sum_w[sub] <= cap) for transitions.
  • Since “using this truck empty” is allowed, start with new_dp = dp[:].
  • The transition destination is nm = mask | sub (with the condition that sub doesn’t overlap with mask).

Compare two subset enumeration methods and use the faster one: - Share fit_list across all states: check sub in fit_list and transition if (sub & mask)==0 - Enumerate subsets of rem for each state: iterate with sub = rem; sub=(sub-1)&rem and transition if sum_w[sub] <= cap

Finally, set dp = new_dp, update reachable, and after processing all trucks, output Yes if dp[full], otherwise No.

(Simple Example) - If \(N=3\), states are mask=0..7. - For example, mask=101(2) means “items 1 and 3 have been loaded,” with remaining rem=010. - If the next truck has sufficient capacity, we can load all of rem and reach full=111.

Complexity

• Time complexity: Typically \(O(2^N + \sum_{j=1}^{M} (\text{reachable count}) \times \min(|\text{fit\_list}_j|, 2^{\text{remaining count}}))\)
  (Roughly \(O(M\cdot 3^N)\) in the worst case, but with \(N\le 15\), reachable state management, enumeration switching, and processing smaller capacities first, it runs fast enough in practice)
• Space complexity: \(O(2^N)\) (dp, sum_w, popc, etc.)

Implementation Notes

• When \(M>N\), keep only the \(N\) largest capacity trucks: Since at most \(N\) trucks will be non-empty, discarding extra small-capacity trucks doesn’t affect the answer.

• Precomputing sum_w[mask] is crucial to make subset weight checks \(O(1)\).

• Processing smaller capacities first keeps reachable states from growing too large, stabilizing the DP.

• Switching enumeration methods (fit_list vs subset enumeration of rem) is the key to optimization, handling both cases when capacity is small and when few items remain.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    W = list(map(int, input().split()))
    C = list(map(int, input().split()))

    full = (1 << N) - 1

    C.sort(reverse=True)
    M = min(M, N)
    C = C[:M]
    if not C:
        print("No")
        return

    if max(W) > max(C):
        print("No")
        return
    if sum(W) > sum(C):
        print("No")
        return

    # Process smaller capacities first to keep reachable states small
    C.sort()

    sum_w = [0] * (1 << N)
    for mask in range(1, 1 << N):
        lsb = mask & -mask
        i = lsb.bit_length() - 1
        sum_w[mask] = sum_w[mask ^ lsb] + W[i]

    popc = [0] * (1 << N)
    for mask in range(1, 1 << N):
        popc[mask] = popc[mask >> 1] + (mask & 1)

    dp = [False] * (1 << N)
    dp[0] = True
    reachable = [0]

    for cap in C:
        # If any current state can finish all remaining items with this truck, done
        for mask in reachable:
            rem = full ^ mask
            if sum_w[rem] <= cap:
                print("Yes")
                return

        fit_list = [sub for sub in range(1, 1 << N) if sum_w[sub] <= cap]
        fit_len = len(fit_list)

        new_dp = dp[:]  # allow leaving this truck empty
        new_reachable = reachable[:]  # start with existing states

        for mask in reachable:
            if mask == full:
                continue

            rem = full ^ mask
            # Choose faster enumeration strategy per state
            if fit_len < (1 << (N - popc[mask])):
                for sub in fit_list:
                    if (sub & mask) == 0:
                        nm = mask | sub
                        if not new_dp[nm]:
                            new_dp[nm] = True
                            new_reachable.append(nm)
            else:
                sub = rem
                while sub:
                    if sum_w[sub] <= cap:
                        nm = mask | sub
                        if not new_dp[nm]:
                            new_dp[nm] = True
                            new_reachable.append(nm)
                    sub = (sub - 1) & rem

        dp = new_dp
        reachable = new_reachable

    print("Yes" if dp[full] else "No")


if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.