Overview

There are \(N\) shopping malls, each containing multiple stores. Shopping at each store yields a “bargain value,” and visiting a mall incurs a transportation cost. Given that you can visit at most \(K\) malls, find the maximum “total profit (sum of bargain values − sum of transportation costs)” you can obtain.

Analysis

The key points in this problem are “which malls to visit” and “which stores to shop at in each mall.”

Strategy for Each Mall

For each shopping mall, we think as follows: - Decide whether to visit the mall (if not visited, there is no profit or cost). - If visiting, it is optimal to select only the stores with “positive bargain values” from all stores in that mall (simply don’t buy items with negative bargain values). - The “net profit” in this case is: $\( \text{net profit} = \left(\sum_{j=1}^{M_i} \max(0, P_{i,j})\right) - C_i \)$

Choosing Which Malls to Visit

Next, we decide which malls to visit, with a maximum of \(K\). It is optimal to select the “top \(K\) malls by net profit (limited to non-negative ones).”

This is because visiting a mall with negative net profit only causes a loss and no gain, so it should not be visited. Also, selecting the top \(K\) by profit maximizes the overall profit.

Let’s look at the following example.

Concrete Example

Input:

3 2
10 3 5 6 7
5 2 3 4
8 2 1 2

We calculate the net profit from the sum of bargain values and transportation cost for each mall: - Mall 1: \((5+6+7) - 10 = 8\) - Mall 2: \((3+4) - 5 = 2\) - Mall 3: \((1+2) - 8 = -5\)

Among these, the malls with non-negative net profit are Mall 1 (8) and Mall 2 (2). Since these are the top 2, visiting both is optimal, with a total profit of \(8 + 2 = 10\).

Choosing Mall 3 with negative profit, or selecting fewer malls, would not increase the profit, so this selection is optimal.

Algorithm

1. For each mall, sum up all positive bargain values among the stores in that mall, then subtract the transportation cost to calculate the “net profit.”
2. Collect the “net profit” of all malls into a list and sort in descending order.
3. Sum only the positive values among the top \(K\) entries to get the answer (ignore negative ones).

Complexity

• Time complexity: \(O\left(\sum_{i=1}^{N} M_i \log M_i + N \log N\right)\)
  • Sorting the bargain values within each mall takes \(O(M_i \log M_i)\)
  • Sorting the list of net profits at the end takes \(O(N \log N)\)
• Space complexity: \(O(N + \sum M_i)\)

Implementation Notes

• The net profit of each mall is computed as “sum of positive bargain values − transportation cost.”

• Don’t forget to select only the top \(K\) malls with non-negative net profit.

• Using sys.stdin.read for fast input reading is recommended (especially to handle cases where \(N\) is large).

  Source Code

import sys
import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx])
    idx += 1
    K = int(data[idx])
    idx += 1
    
    malls = []
    for _ in range(N):
        C = int(data[idx])
        idx += 1
        M = int(data[idx])
        idx += 1
        P = []
        for _ in range(M):
            p = int(data[idx])
            idx += 1
            P.append(p)
        # 各モールで得られる純利益（お得度の合計 - 交通費）を計算
        profit = sum(P) - C
        # お得度を降順にソートして、先頭から選べるようにする
        P.sort(reverse=True)
        malls.append((profit, P, C))
    
    # 各モールのお得度の累積和を前計算
    cum_profits = []
    for profit, P, C in malls:
        cum = [0]
        for p in P:
            cum.append(cum[-1] + p)
        cum_profits.append((cum, C))
    
    # 各モールの純利益でソート（降順）
    # 各要素: (純利益, cum配列, 交通費C)
    sorted_malls = []
    for i in range(N):
        profit, P, C = malls[i]
        cum, _ = cum_profits[i]
        sorted_malls.append((profit, cum, C))
    
    sorted_malls.sort(reverse=True)
    
    max_total = 0
    # 訪れるモールの数 k を 0 から K まで試す
    # ただし、k個のモールを選ぶときに、純利益が高い上位k個を選ぶのが最適
    # しかし、純利益=sum(P)-C なので、単純にこれでソートしても最適ではない可能性がある
    # 実際には、選ぶモールの組み合わせと、各モールで買う商品の数を考慮する必要がある
    
    # より正確には、各モールについて「訪問する場合の最大利益」を計算し、
    # それを基に上位K個を選ぶのが良い
    
    # 各モールの利益を「そのモールに訪問したとき得られる最大利益」として定義
    # それは、そのモール内の商品をいくつか選んで買うことで最大化される
    # つまり、各商品のお得度が正なら買うべき。負なら買わない
    
    # 各モールの「純利益」を再定義：そのモールに訪問したときに得られる最大利益（非負）
    profits = []
    for _, P, C in malls:
        gain = sum(max(0, p) for p in P)
        net_profit = gain - C
        profits.append(net_profit)
    
    # 上位K個の非負の利益を選ぶ
    profits.sort(reverse=True)
    current_sum = 0
    for i in range(K):
        if profits[i] > 0:
            current_sum += profits[i]
        else:
            break
    max_total = current_sum
    
    print(max_total)

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.