Overview

This problem involves summarizing each shopping mall by its “net profit when visited (sum of store profits − transportation cost)” and maximizing the total when selecting the top \(K\) malls with the highest net profits.

Analysis

Key Insight

• When visiting mall \(i\), you can choose any number of stores you like within the same mall (including 0 stores).
• However, since the constraint states \(P_{i,j} \ge 1\), if you visit a mall, it’s optimal to buy from all profitable stores.
  There’s no reason not to buy (since buying always increases the total profit).

Therefore, the contribution to the total profit when visiting mall \(i\) can be expressed as: - Sum of store profits \(S_i = \sum_{j=1}^{M_i} P_{i,j}\) - Transportation cost \(C_i\)

The net profit is: $\( \text{net}_i = S_i - C_i \)$

Handling the “Don’t Visit” Option

• If \(\text{net}_i \le 0\), visiting that mall provides no benefit (it’s better not to visit).
• Therefore, only malls with \(\text{net}_i > 0\) need to be considered as candidates to visit.

Problem Reformulation

• From the array of positive values \(\text{net}_i\) (net profit per mall), select at most \(K\) items to maximize the total.

The optimal strategy is simply: - Take at most \(K\) items in order of highest net profit

Pitfalls of the Naive Approach

• Sorting all \(\text{net}_i\) values in an array takes \(O(N \log N)\), which often fits within the time limit for these constraints, but:
  • It uses extra memory
  • The input contains up to \(10^5\) store information entries, making I/O heavy
    For these reasons, implementation-dependent slowdowns can occur.
• Instead, using a heap to manage only the top \(K\) items allows you to keep only what’s needed, making it more efficient.

(Example) - If \(K=2\) and net profits are \([5, 1, 7, 3]\), the top 2 are \(7\) and \(5\), so the answer is \(12\).

Algorithm

1. For each mall \(i\), sum all store profit values to create \(S_i\).
2. Calculate \(\text{net}_i = S_i - C_i\).
3. Only when \(\text{net}_i > 0\), insert into a min-heap of maximum size \(K\) to maintain the “top \(K\)”.
   • If the heap has fewer than \(K\) elements, push
   • If there are already \(K\) elements, replace only if the new value is larger than the heap’s minimum (the smallest value in the top set)
4. Finally, the sum of elements in the heap is the answer (maximum sum of net profits from visited malls).

Why use a min-heap: - When managing the “top \(K\)”, the element we most want to discard is the minimum in that set - A min-heap allows immediate access to the minimum element (\(O(1)\) lookup, \(O(\log K)\) replacement)

Complexity

• Time Complexity:
  Let \(T=\sum M_i\) be the total number of store entries. Reading each store takes \(O(T)\), and heap operations occur at most once per mall, taking \(O(N \log K)\).
  Overall:
  $\(O(T + N \log K)\)$
• Space Complexity:
  The heap holds at most \(K\) elements:
  $\(O(K)\)$

Implementation Notes

• If you visit, buy from all stores (this works because \(P_{i,j} \ge 1\)), so for each mall, you only need to calculate the “sum \(S_i\)”.

• \(\text{net}_i \le 0\) only worsens the answer, so it can be ignored.

• Since the input size is large, the code uses sys.stdin.buffer.read() with a fast integer parser (int_reader) to speed up I/O.

• Python’s heap uses heapq (min-heap), and by keeping the size at \(K\), we avoid unnecessary storage and sorting.

  Source Code

import sys
import heapq

def int_reader():
    data = sys.stdin.buffer.read()
    num = 0
    sign = 1
    in_num = False
    for b in data:
        if 48 <= b <= 57:
            num = num * 10 + (b - 48)
            in_num = True
        else:
            if in_num:
                yield sign * num
                num = 0
                sign = 1
                in_num = False
            elif b == 45:  # '-'
                sign = -1
    if in_num:
        yield sign * num

def main():
    it = int_reader()
    N = next(it)
    K = next(it)

    heap = []  # min-heap for top-K positive net profits

    for _ in range(N):
        C = next(it)
        M = next(it)
        s = 0
        for _ in range(M):
            s += next(it)
        net = s - C
        if net > 0:
            if len(heap) < K:
                heapq.heappush(heap, net)
            elif net > heap[0]:
                heapq.heapreplace(heap, net)

    print(sum(heap))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.