Overview

This is a problem where you optimally choose “which items to check out together at the supermarket” to maximize the discount and minimize the total payment. The essence is “how to construct the total price \(X\) of items paid at the supermarket,” and ultimately it suffices to greedily select items in descending order of price.

Analysis

Let the total be \(S=\sum C_j\) and the sum of items checked out at the supermarket be \(X\). Then the total payment is

[ (S - X) + \left(X - \left\lfloor \frac{X P(X)}{100} \right\rfloor\right) = S - \left\lfloor \frac{X P(X)}{100} \right\rfloor ]

where \(P(X)\) is the discount rate of the tier applied to \(X\). In other words, what we need to minimize is

[ S - \text{discount}(X) ]

so effectively we just need to maximize the discount amount \(\left\lfloor X P(X)/100 \right\rfloor\).

---

The difficulty here is that the achievable values of \(X\) are “subset sums of the items.” Naively trying all subsets is \(2^N\), which is infeasible.

Key observation:

• The discount rate is non-decreasing as tiers increase (\(P_1 \le \cdots \le P_K\))
• Within the same tier, \(P\) is constant, so a larger \(X\) yields a larger discount
• Therefore, when we decide to “bring \(m\) items to the supermarket,” it is advantageous to maximize the sum \(X\)
• To maximize the sum, it is optimal to select the \(m\) most expensive items

Thus, the only candidates for \(X\) we need to examine are “the prefix sums of the first \(m\) items when sorted in descending order” (\(m=0..N\)).

This reduces the number of candidates to \(N+1\). For each candidate, we determine the applicable tier to get the answer. Furthermore, since the prefix sums are monotonically increasing, the tier pointer only needs to be advanced forward.

Algorithm

1. Sort the item price array \(C\) in descending order.
2. Compute the total \(S=\sum C_j\). Initialize the answer as \(S\) (the case \(X=0\), buying nothing at the supermarket).
3. Start \(prefix\) (the cumulative sum from the beginning) at \(0\).
4. For \(m=1..N\):
   • \(prefix += C[m-1]\) (this is the candidate \(X\))
   • Update the pointer to find the largest \(i\) such that \(T_i \le prefix\) in the tier array \(T\)
   • Compute the discount \(\text{discount}=\left\lfloor prefix \cdot P_i / 100 \right\rfloor\)
   • Compute the total payment \(\text{cost}=S-\text{discount}\) and update the minimum
5. Output the minimum.

This approach matches the provided code.

Complexity

• Time complexity: \(O(N \log N + K)\) (Sorting \(O(N\log N)\), cumulative scan \(O(N)\), tier pointer advancement \(O(K)\) in total)
• Space complexity: \(O(N + K)\)

Implementation Notes

• \(X=0\) (buying nothing at the supermarket) is also a valid option, so the initial value ans = total is necessary.

• For the tier search, binary search each time would also work, but since prefix is monotonically increasing, advancing a pointer is faster and more concise.

• Since amounts can become very large, be careful about integer overflow (not an issue in Python).

• The discount amount must always be computed with // 100 (floor division).

  Source Code

import sys

def main():
    input = sys.stdin.readline

    N, K = map(int, input().split())
    arr = list(map(int, input().split()))
    T = [0] * K
    P = [0] * K
    for i in range(K):
        T[i] = arr[2 * i]
        P[i] = arr[2 * i + 1]

    C = list(map(int, input().split()))
    C.sort(reverse=True)

    total = sum(C)
    ans = total  # X = 0 も可能

    prefix = 0
    j = 0  # 現在のティア index（T[j] <= prefix を満たす最大）
    for x in C:
        prefix += x
        while j + 1 < K and T[j + 1] <= prefix:
            j += 1
        discount = (prefix * P[j]) // 100
        cost = total - discount
        if cost < ans:
            ans = cost

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.3-codex.