この問題は最小費用流に帰着して解くことができます。

この問題は「来場者 \(i\) と商品 \(j\) をマッチングさせると \(X_{i,j}\) 点を得る」という最大重み二部マッチング問題とみなすことができます。一般に、最大重み二部マッチング問題は、次のようにして最小費用流問題に帰着することができます。

• 2 つの部集合をそれぞれ \(A,B\) とし、\(A_i\) と \(B_j\) をマッチングさせたときの利得を \(X_{i,j}\) であるとする。
• \(S\) から \(A_i\) へ、容量 1、費用 0 の辺をはる
• \(A_i\) から \(B_j\) へ、容量 1、費用 \(\mathrm{BIG}-X_{i,j}\) の辺をはる
  • \(\mathrm{BIG}\) は、全ての \(i,j\) で \(\mathrm{BIG}-X_{i,j} \geq 0\) を満たす定数とする
• \(B_j\) から \(T\) へ、容量 1、費用 0 の辺をはる
• \(S\) から \(T\) への流量 \(f\) の最小費用を \(\mathrm{cost}_f\) とするとき、\(\max_f (f*\mathrm{BIG}-\mathrm{cost}_f)\) が求める最大重みである

頂点数 \(N\)、辺数 \(M\) のとき、流量 \(f\leq F\) の全ての \(f\) に対する最小費用流は \(O(F(N+M)\log (N+M))\) で求めることができます。よってこの問題は \(O(M(N+M)\log (N+M))\) で解くことができました。

ACL(AtCoder Library)を用いると簡単に実装することができます。

実装例 (C++)

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

int main(){
  int n, m;
  cin >> n >> m;
  vector<int> c(m);
  for(int i=0; i<m; i++) cin >> c[i];
  vector<vector<int>> v(n, vector<int>(m));
  for(int i=0; i<n; i++)for(int j=0; j<m; j++) cin >> v[i][j];
  
  atcoder::mcf_graph<int,long long> g(n+m+2);
  //n+m:source, n+m+1:sink, 0-(n-1):n, n-(n+m):m
  for(int i=0; i<n; i++){
    g.add_edge(n+m, i, 1, 0);
  }
  for(int j=0; j<m; j++){
    g.add_edge(n+j, n+m+1, 1, 0);
  }
  for(int i=0; i<n; i++)for(int j=0; j<m; j++){
    g.add_edge(i, n+j, 1, 1e9-(v[i][j]-c[j]));
  }
  auto ret = g.slope(n+m, n+m+1);
  long long ans = 0;
  for(auto[flow, cost]: ret){
    ans = max(ans, flow*(long long)1e9-cost);
  }
  cout << ans << endl;
}

実装例 (Python)

from atcoder.mincostflow import MCFGraph

N, M = map(int, input().split())
C = list(map(int, input().split()))
V = [list(map(int, input().split())) for _ in range(N)]

g = MCFGraph(N+M+2)
for i in range(N):
  g.add_edge(N+M, i, 1, 0)
for j in range(M):
  g.add_edge(N+j, N+M+1, 1, 0)
for i in range(N):
  for j in range(M):
    if V[i][j] > C[j]:
      g.add_edge(i, N+j, 1, 10**9-(V[i][j]-C[j]))
ret = g.slope(N+M, N+M+1)
ans = max(flow * 10**9 - cost for flow, cost in ret)
print(ans)

なお、この問題は bitDPにより解くこともできます。例えばgeminiによる解説を参照ください。