Overview

Since \(N \leq 20\) is small, we use bit DP where the set of items is represented by a bitmask.
For each subset, we maintain the “current truck’s load” and the “number of trucks used and finished so far” to find the minimum number of trucks required.

Analysis

This problem asks us to divide the items into several groups such that the total weight of each group is at most \(M\), minimizing the number of groups.

In other words, each group corresponds to one truck.

A naive approach would be to brute-force which truck each item is placed on, but there are too many ways to partition them, so a simple brute-force will not run in time.

Also, a greedy approach like “process items in order and load them into the current truck if they fit” is incorrect.

For example, if \(M=10\) and the items are

\(4, 8, 2, 6\)

packing them in the input order gives:

• 1st truck: \(4\)
• 2nd truck: \(8+2=10\)
• 3rd truck: \(6\)

which seems to require 3 trucks.

However, we can pack them as:

• 1st truck: \(4+6=10\)
• 2nd truck: \(8+2=10\)

which only requires 2 trucks.

Therefore, we need to search efficiently, taking the order of loading items into account.

Since \(N \leq 20\), there are at most

\(2^{20}\)

subsets of items.
This is about 1 million states, so we can use subset DP (bit DP).

Algorithm

We represent the set of loaded items using a bitmask.

• If the \(i\)-th bit of \(mask\) is \(1\), item \(i\) has already been loaded.
• If it is \(0\), it has not been loaded yet.

In the DP, we maintain the following information for each \(mask\):

• The number of trucks already fully loaded and finished.
• The current load of the truck currently being loaded.

For example, let the state be \((c, x)\):

• \(c\): the number of completed trucks before the current one.
• \(x\): the weight currently loaded on the current truck.

In this case, the final number of trucks used is \(c+1\).

However, there can be multiple possible states for the same \(mask\).
Among them, a state is better if:

1. The number of completed trucks \(c\) is smaller.
2. If \(c\) is the same, the current load \(x\) is smaller.

This is because a smaller current load means more remaining capacity, making it easier to load future items.

Therefore, it is sufficient to store only the best \((c, x)\) for each \(mask\).

Transitions

Suppose the current state is \(mask\), and we load an unloaded item \(i\) next.

Let the current truck’s load be \(x\) and the weight of item \(i\) be \(W_i\).

If it fits in the current truck

If \(x + W_i \leq M\), we load it onto the same truck.

The state becomes:

\((c, x + W_i)\)

If it does not fit in the current truck

If \(x + W_i > M\), we use a new truck.

Since the current truck is now completed, the number of finished trucks increases by 1.

The state becomes:

\((c+1, W_i)\)

We perform this transition for all \(mask\) and all unloaded items.

Representing States in Code

In the code, we encode \((c, x)\) into a single integer:

base = M + 1
value = c * base + x

Since \(0 \leq x \leq M\), setting \(base = M + 1\) allows us to compare the encoded integers directly. The integer comparison naturally corresponds to:

1. Smaller \(c\) first.
2. If \(c\) is the same, smaller \(x\) first.

In other words, we can select the better state simply by:

if cand < dp[nmask]:
    dp[nmask] = cand

Finally, letting full be the state where all items are loaded,

dp[full] // base

represents the number of completed trucks \(c\).
Since the current truck also counts as 1 truck, the answer is:

dp[full] // base + 1

Complexity

There are \(2^N\) subsets.
For each subset, we try at most \(N\) unloaded items.

• Time Complexity: \(O(N2^N)\)
• Space Complexity: \(O(2^N)\)

Since \(N \leq 20\), this is well within the time limit.

Implementation Details

dp[mask] stores the encoded value.

base = M + 1
dp[0] = 0

This represents the initial state:

• Number of completed trucks: \(0\)
• Current load: \(0\)

assuming we start with one empty truck.

Also, the value with only the \(i\)-th item’s bit set is 1 << i.
In the code, we make it possible to quickly look up the weight of the item corresponding to that bit:

bit_w = [0] * size
for i, w in enumerate(W):
    bit_w[1 << i] = w

The unused items can be found with:

rem = full ^ mask

Then, we can extract one bit of the unused items using:

b = rem & -rem

This allows us to efficiently iterate through the bits.

Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M = data[0], data[1]
    W = data[2:]

    if N == 0:
        print(0)
        return
    if sum(W) <= M:
        print(1)
        return

    size = 1 << N
    full = size - 1
    base = M + 1
    INF = (N + 1) * base

    dp = [INF] * size
    dp[0] = 0

    bit_w = [0] * size
    for i, w in enumerate(W):
        bit_w[1 << i] = w

    for mask in range(size):
        val = dp[mask]
        load = val % base
        space = M - load
        opened = val - load + base
        rem = full ^ mask

        while rem:
            b = rem & -rem
            w = bit_w[b]
            nmask = mask + b

            if w <= space:
                cand = val + w
            else:
                cand = opened + w

            if cand < dp[nmask]:
                dp[nmask] = cand

            rem ^= b

    print(dp[full] // base + 1)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.