Summary

This problem can be modeled as “bipartite matching with profits” connecting visitors and products.
Since each visitor and each product can be used at most once, we maximize the total profit among valid transaction sets.

Analysis

Let the profit when selling product \(j\) to visitor \(i\) be:

\(P_{i,j} = V_{i,j} - C_j\)

However, transactions with \(P_{i,j} < 0\) are forbidden.
Also, transactions with \(P_{i,j} = 0\) do not increase the profit and only consume a visitor and a product, so they are unnecessary for the optimal solution.
Therefore, it is sufficient to consider only transactions with \(P_{i,j} > 0\).

This problem can be formulated as the following bipartite graph problem:

• Left side: Visitors
• Right side: Products
• Edges: Transactions with positive profits
• Each vertex can be used at most once
• Maximize the sum of profits of the chosen edges

This is “maximum weight bipartite matching”.

Why a Naive Approach is Difficult

Simply choosing transactions greedily from the largest profit fails.

For example, consider the following profits:

	Product 1	Product 2
Visitor A	100	99
Visitor B	98	None

If we greedily choose “sell Product 1 to Visitor A”, which is the transaction with the maximum profit, the total profit is \(100\).

However, in reality, if we do:

• Sell Product 2 to Visitor A: profit \(99\)
• Sell Product 1 to Visitor B: profit \(98\)

The total profit is \(197\).

Therefore, locally choosing the best transaction does not yield the global optimum.

Also, “selling as many as possible” is not always correct, because we might have to sacrifice a high-profit transaction to sell more.

Thus, we will solve this using minimum cost flow.

Algorithm

Minimum cost flow is an algorithm to “minimize the sum of costs”. On the other hand, in this problem, we want to “maximize the sum of profits”.

Therefore, we convert profits into costs.

Let the maximum value of positive profits be:

\(B = \max P_{i,j}\)

We define the cost of each transaction as:

\(B - P_{i,j}\)

Then, transactions with larger profits will have smaller costs.
Also, since \(B\) is the maximum profit, all costs will be greater than or equal to \(0\).

Graph Construction

We construct the following flow network:

• Source \(S\)
• Vertices representing visitors
• Vertices representing products
• Sink \(T\)

Edges are added as follows:

1. \(S \to\) visitor \(i\)

   • Capacity \(1\)
   • Cost \(0\)

2. visitor \(i \to\) product \(j\)

   • Added only when profit \(P_{i,j} > 0\)
   • Capacity \(1\)
   • Cost \(B - P_{i,j}\)

3. product \(j \to T\)

   • Capacity \(1\)
   • Cost \(0\)

In this setup, a flow of \(1\) unit:

\(S \to\) visitor \(i \to\) product \(j \to T\)

corresponds to “selling product \(j\) to visitor \(i\)”.

Since all capacities are \(1\), the conditions:

• Each visitor can buy at most \(1\) product
• Each product can be sold to at most \(1\) person

are naturally satisfied.

Profit Reconstruction

Suppose the flow is \(k\) and the minimum cost at that flow is \(\mathrm{cost}\).

Since the cost of each chosen transaction is \(B - P_{i,j}\), the total cost is:

\(\mathrm{cost} = kB - \text{total profit}\)

Therefore, the total profit can be reconstructed as:

\(kB - \mathrm{cost}\)

Why Use slope?

If we push the maximum flow in a standard minimum cost flow, it will result in a solution that “sells as much as possible”. However, in this problem, we can freely choose the number of items to sell.

Therefore, we find the minimum cost for each flow \(0, 1, 2, \dots, M\), and find the one that maximizes:

\(kB - \mathrm{cost}\)

Using mcf_graph::slope(S, T, M) from the AtCoder Library allows us to obtain information on the minimum cost for each flow. We calculate the profit for each returned pair \((\mathrm{flow}, \mathrm{cost})\) and take the maximum.

Complexity

Let the number of vertices be \(V = N + M + 2\) and the number of edges be \(E\).
Since there are at most \(NM\) edges with positive profits:

\(E = O(NM + N + M)\)

Since the maximum amount of flow is at most the number of products \(M\), the complexity of the minimum cost flow is roughly:

• Time complexity: \(O(ME \log V)\)
• Space complexity: \(O(V + E)\)

Given the constraints \(M \leq 14\) and \(NM \leq 2 \times 10^5\), this is sufficiently fast.

Implementation Details

• Do not add edges with profit \(P_{i,j} \leq 0\).

  • \(P_{i,j} < 0\) is a forbidden transaction.
  • \(P_{i,j} = 0\) does not increase the profit, so it is unnecessary.

• base is used as the maximum value of positive profits.

  • By setting the cost to base - profit, we can convert it into a minimum cost flow with non-negative costs.

• The answer is reconstructed as flow * base - cost.

• Since the profit can be \(0\) when no products are sold, initialize the answer to \(0\).

  Source Code

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<long long> C(M);
    for (int j = 0; j < M; j++) cin >> C[j];

    vector<tuple<int, int, long long>> edges;
    vector<char> has_edge(N, 0);
    long long base = 0;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            long long V;
            cin >> V;
            long long profit = V - C[j];
            if (profit > 0) {
                edges.emplace_back(i, j, profit);
                has_edge[i] = 1;
                base = max(base, profit);
            }
        }
    }

    int S = N + M;
    int T = S + 1;

    atcoder::mcf_graph<int, long long> g(N + M + 2);

    for (int i = 0; i < N; i++) {
        if (has_edge[i]) g.add_edge(S, i, 1, 0);
    }

    for (auto [i, j, profit] : edges) {
        g.add_edge(i, N + j, 1, base - profit);
    }

    for (int j = 0; j < M; j++) {
        g.add_edge(N + j, T, 1, 0);
    }

    auto res = g.slope(S, T, M);

    long long ans = 0;
    for (auto [flow, cost] : res) {
        ans = max(ans, (long long)flow * base - cost);
    }

    cout << ans << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-high.