Overview

This problem is a “maximum weight bipartite matching” problem where we want to maximize the profit obtained between products and visitors. By focusing on the characteristic that the number of products \(M\) is extremely small (\(M \leq 14\)), we can solve this problem quickly within the time limit by filtering the effective visitors first and then applying bitmask DP (dynamic programming).

---

Observations

1. Naive Approach and Its Limitations

Each product can be sold to at most one person, and each visitor can buy at most one product. This has the structure of bipartite matching. The number of visitors \(N\) is up to \(10^5\), and the number of products \(M\) is up to \(14\).

If we consider a DP (bitmask DP) over all visitors, where the state is “the maximum profit after considering up to the \(i\)-th visitor with the set of sold products being \(S\)”, the number of states is \(2^M\) and the transitions take \(M\) ways. This results in an overall time complexity of \(O(N \cdot M \cdot 2^M)\). When \(M = 14\), \(2^{14} = 16384\). Multiplying this by \(N = 10^5\) makes the number of operations exceed \(10^9\), which will not run within the time limit (resulting in TLE).

2. Crucial Observation: Filtering the Visitors

There are only \(M\) products in total. Therefore, at most \(M\) visitors will actually purchase a product. From this, we realize that we do not need to consider all visitors; it is sufficient to extract only a subset of visitors who have a very high likelihood of purchasing.

Specifically, for each product \(j\), we only keep the top \(M\) visitors with the highest positive profit (\(V_{i,j} - C_j > 0\)) as candidates. Why is the top \(M\) enough? Consider a product \(j\) and a visitor \(x\) whose profit for product \(j\) is ranked \((M+1)\)-th or lower. Even if there exists an optimal assignment where product \(j\) is sold to visitor \(x\), at least one of the top \(M\) visitors must be left without any product assigned to them (since there are at most \(M\) products in total). If we change the assignment to sell product \(j\) to that unassigned top visitor instead, the total profit will always increase (or stay the same).

Therefore, we can always find the optimal assignment by considering only the top \(M\) visitors for each product, which is at most \(M \times M = M^2\) visitors in total. When \(M \le 14\), \(M^2 \le 196\), dramatically reducing the number of visitors to consider from \(10^5\) to at most 196.

---

Algorithm

Step 1: Candidate Selection

1. For each product \(j \in [0, M-1]\), list all visitors \(i\) with positive profit \(V_{i,j} - C_j > 0\).
2. Sort this list in descending order of profit, and add the top \(M\) visitor IDs to a set candidates (removing duplicates).
3. Let the size of the extracted candidate set be \(K\) (\(K \leq M^2\)).

Step 2: Running the Bitmask DP

For the \(K\) selected candidates, we perform DP to decide whether to assign a product to each person one by one.

• DP Table Definition: dp[s]: The maximum profit when the set of already sold products is \(s\) (represented as a bitmask).

• Initialization: dp[0] = 0, and all other states are initialized to \(0\).

• Transitions: For each candidate \(k\) (\(0 \le k < K\)), we update the DP table sequentially. Loop through the product sets \(s\) in descending order from \((2^M - 1)\) down to \(1\) (Note: If we update in ascending order, we might sell multiple products to the same candidate. We must iterate in descending order to prevent this duplicate assignment).

The transition when candidate \(k\) buys product \(j\) (where \(j \in s\)) is as follows: $\(dp[s] = \max(dp[s], dp[s \setminus \{j\}] + \text{profit}(k, j))\)\( Where \)\text{profit}(k, j) = V_{k,j} - C_j$.

---

Complexity

Time Complexity

1. Candidate Selection: For each product, we calculate the profits for all \(N\) visitors and sort them, which takes \(O(M \cdot N \log N)\) time.
2. Running the DP: For \(K \le M^2\) candidates, the number of states is \(2^M\), and the number of transitions from each state (the number of products for which a candidate can get a positive profit) is at most \(M\). Thus, the DP part takes \(O(M^3 \cdot 2^M)\) time.

The overall time complexity is \(O(M \cdot N \log N + M^3 \cdot 2^M)\). When \(N = 10^5\) and \(M = 14\): - Sorting part: \(14 \times 10^5 \log_2(10^5) \approx 2.3 \times 10^7\) operations - DP part: \(14^3 \times 16384 \approx 4.5 \times 10^7\) operations This can easily run in less than 1 second, even in Python.

Space Complexity

The size of the DP table is \(2^M\). Additionally, storing the input data and the candidate list uses \(O(N \cdot M)\) memory. The overall space complexity is \(O(N \cdot M + 2^M)\), which is extremely safe within the memory limit.

---

Implementation Details

• Optimizing DP Speed (Constant-Factor Optimization): For each candidate, we pre-list only the products that yield a positive profit (“active” products). In the DP transitions, we only loop over these active products. This allows us to skip useless transitions (transactions with a profit of \(0\) or less, or transactions that do not need to be considered at all), significantly reducing the execution time.

• 1D Array DP (In-place Updates): By looping through the set \(s\) in descending order (range((1 << M) - 1, 0, -1)), we can overwrite the states from the previous candidate. This allows us to correctly enforce the constraint that “each visitor buys at most one product” using only a 1D array.

  Source Code

import sys


def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    M = int(input_data[1])

    C = [int(x) for x in input_data[2 : 2 + M]]
    V_flat = [int(x) for x in input_data[2 + M :]]

    candidates = set()
    for j in range(M):
        cj = C[j]
        lst = []
        for i in range(N):
            val = V_flat[i * M + j] - cj
            if val > 0:
                lst.append((val, i))
        lst.sort(reverse=True)
        for val, i in lst[:M]:
            candidates.add(i)

    cand_list = list(candidates)
    K = len(cand_list)

    active_j_list = []
    for i in cand_list:
        active = []
        for j in range(M):
            val = V_flat[i * M + j] - C[j]
            if val > 0:
                active.append((j, val))
        active_j_list.append(active)

    dp = [0] * (1 << M)

    for k in range(K):
        active = active_j_list[k]
        if not active:
            continue
        for s in range((1 << M) - 1, 0, -1):
            dp_s = dp[s]
            for j, val in active:
                if s & (1 << j):
                    prev = dp[s ^ (1 << j)] + val
                    if prev > dp_s:
                        dp_s = prev
            dp[s] = dp_s

    print(dp[(1 << M) - 1])


if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3.5-flash-high.