Summary

This problem asks us to maximize the total profit \(V_{i,j} - C_j\) (only considering non-negative profits) under the condition that there are \(N\) visitors and \(M\) items, where each visitor can be assigned at most \(1\) item, and each item can be assigned to at most \(1\) visitor. This is a classic bipartite matching (assignment problem), but since the number of items is very small (\(M \leq 14\)), we can solve it using bitmask DP.

Analysis

Conversion to Profit

First, the profit from selling item \(j\) to visitor \(i\) is \(V_{i,j} - C_j\). We can precompute a profit table as prof[i][j] = V[i][j] - C[j]. Since transactions with negative profits are not allowed, we cannot choose pairs with prof[i][j] < 0.

Issues with a Naive Approach

If we use “which item is assigned to each visitor” as the state, the state space becomes huge because the number of visitors is large (\(N \leq 10^5\)). On the other hand, since there are only \(M \leq 14\) items, we can represent “which items have been sold” using a bitmask. This keeps the number of states down to \(2^M \leq 2^{14} = 16384\).

However, if we process all visitors in the DP transitions, the complexity would be \(O(N \cdot 2^M \cdot M)\), which is too slow for \(N = 10^5\).

Important Observation: Filtering Candidate Visitors

Here is the key observation:

In the final matching, at most \(M\) visitors will actually buy an item.

Therefore, when considering item \(j\), the only visitors who are actually relevant as “potential buyers of item \(j\)” are the top \(M\) visitors with the highest profit for item \(j\). This is because, even considering conflicts with other items, only one visitor will be assigned to item \(j\), and this visitor will never be chosen from outside the top \(M\) candidates. Even if some of these top \(M\) visitors are assigned to other items (at most \(M-1\) other items), there will always be at least one visitor remaining from the top \(M\) candidates. Thus, we can find the optimal solution by only considering these top \(M\) candidates.

If we mark the top \(\min(N, M)\) visitors as candidates for each item, the total number of candidate visitors drastically reduces to at most \(M^2 \leq 196\).

Algorithm

1. Create the profit table: prof[i][j] = V[i][j] - C[j].

2. Filter candidates: For each item \(j\), select the top \(\min(N, M)\) visitors in descending order of prof[i][j] (using partial_sort). If the profit is non-negative, mark that visitor as a candidate in chosen.

3. Bitmask DP: Let dp[mask] be “the maximum profit when the set of sold items is mask”. Initialize dp[0] = 0.

   • Process each candidate visitor ci one by one. Since each visitor can buy at most \(1\) item, we copy dp to ndp and perform transitions representing “visitor ci newly buys item \(j\)”: $\(\text{ndp}[mask | (1 \ll j)] \leftarrow \max(\cdots,\ dp[mask] + \text{prof}[ci][j])\)\( Here, we transition only if `mask` does not already contain \)j$, and prof[ci][j] >= 0.
   • By replacing the dp array with ndp after processing each visitor, we naturally satisfy the constraint “at most one item per visitor”.

4. Answer: The maximum value of dp[mask] over all mask (including \(0\) for selling nothing).

Intuition behind Transitions

For each visitor, we start with ndp = dp (representing the choice of not buying anything), and only add transitions representing “buying item \(j\)”. Since we finish processing one visitor before moving to the next, no visitor is counted twice, ensuring that “each visitor gets at most \(1\) item”.

Complexity

Let \(K\) be the number of candidate visitors, where \(K = O(M^2)\).

• Time Complexity:
  • Filtering candidates: Performing partial_sort for each item takes about \(O(M \cdot N \log M)\).
  • Bitmask DP: \(O(K \cdot 2^M \cdot M) = O(M^3 \cdot 2^M)\).
  • Overall time complexity is around \(O(N M \log M + M^3 \cdot 2^M)\), which is fast enough under the given constraints.
• Space Complexity: \(O(N M + 2^M)\).

Implementation Details

• Negative Profit Check: Since negative-profit transactions are forbidden, you must exclude cases where prof < 0 during both candidate selection and DP transitions.

• Overflow Prevention: Since \(V\) and \(C\) can be up to \(10^9\), and there are up to \(14\) items, the total profit can reach up to \(1.4 \times 10^{10}\), which overflows a standard 32-bit int. Use 64-bit integers (long long). It is also safer to initialize the DP table (representing unreachable states) with a sufficiently small negative value like LLONG_MIN/2 to prevent overflow when adding values.

• Using partial_sort: You do not need to sort the entire array. Finding only the top \(\min(N, M)\) elements is sufficient, so using partial_sort helps save computation time.

• Filtering Candidates is Key to Correctness: The core observation of this problem is that “since there are at most \(M\) matched pairs, we only need to look at the top \(M\) visitors for each item.” Skipping this step will result in TLE (Time Limit Exceeded) when the number of visitors is large.

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, M;
    scanf("%d %d", &N, &M);
    vector<long long> C(M);
    for(int j=0;j<M;j++) scanf("%lld",&C[j]);
    
    vector<vector<long long>> prof(N, vector<long long>(M));
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            long long v; scanf("%lld",&v);
            prof[i][j]=v-C[j];
        }
    }
    
    // For each product, keep top M visitors by profit (>=0).
    // In any matching (at most M products), only these candidates matter.
    vector<char> chosen(N,0);
    for(int j=0;j<M;j++){
        vector<int> idx(N);
        iota(idx.begin(), idx.end(), 0);
        int k = min(N, M);
        partial_sort(idx.begin(), idx.begin()+k, idx.end(),
                     [&](int a,int b){ return prof[a][j] > prof[b][j]; });
        for(int t=0;t<k;t++){
            if(prof[idx[t]][j] >= 0) chosen[idx[t]] = 1;
        }
    }
    
    vector<int> cand;
    for(int i=0;i<N;i++) if(chosen[i]) cand.push_back(i);
    
    int full = 1<<M;
    const long long NEG = LLONG_MIN/2;
    vector<long long> dp(full, NEG);
    dp[0]=0;
    
    for(int ci : cand){
        vector<long long> ndp = dp;
        for(int mask=0; mask<full; mask++){
            if(dp[mask]==NEG) continue;
            long long base = dp[mask];
            for(int j=0;j<M;j++){
                if(mask&(1<<j)) continue;
                long long p = prof[ci][j];
                if(p<0) continue;
                int nm = mask|(1<<j);
                if(base+p > ndp[nm]) ndp[nm] = base+p;
            }
        }
        dp = ndp;
    }
    
    long long ans = 0;
    for(int mask=0; mask<full; mask++) ans = max(ans, dp[mask]);
    printf("%lld\n", ans);
    return 0;
}

---

This editorial was generated by claude4.8opus-high.