概要

総支払額は「全商品の合計金額」から「スーパーで受けられる割引額」を引いた形になります。
したがって、この問題は「どの部分集合を選ぶか」ではなく、「割引額が最大になるのはいつか」を考える問題です。

考察

まず、全商品の定価の合計を \(S\) 円とします。

スーパーで買う商品の合計を \(X\) 円とすると、残り \(S-X\) 円分は別の店で定価購入です。
このとき総支払額は

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

となります。ここで \(P_i\) は、\(X\) に対応するティアの割引率です。

つまり、\(S\) は固定なので、総支払額を最小化するには割引額 $\( \left\lfloor \frac{X \times P_i}{100} \right\rfloor \)$ を最大化すればよいことが分かります。

---

重要な気づき

ここで、スーパーで買う金額 \(X\) を大きくするとどうなるか考えます。

• \(X\) が増えると、適用されるティアは同じか上がる
• 割引率 \(P_i\) はティアが上がるほど下がらない（\(P_1 \leq P_2 \leq \cdots \leq P_K\)）
• よって、\(\displaystyle \frac{X \times P_i}{100}\) は \(X\) を増やすほど小さくならない
• 切り捨て \(\lfloor \cdot \rfloor\) をしても、割引額は減らない

つまり、スーパーで買う商品の合計金額 \(X\) が大きいほど、割引額は小さくならないです。

したがって、割引額を最大にする最善の選び方は

\[ X = S \]

すなわち、すべての商品をスーパーで買うことです。

---

素朴なアプローチが不要な理由

問題文だけ見ると、

• どの商品の組み合わせをスーパーで買うか
• 部分集合和を考える必要があるか

と思ってしまいます。

しかし、\(N \leq 2 \times 10^5\) なので、部分集合を全探索するのはもちろん不可能ですし、部分和 DP も金額が大きすぎて使えません。

ですがこの問題では、上の単調性の考察により、部分集合を一切考える必要がありません。
全商品の合計 \(S\) を求め、その金額に対応するティアで割引を計算するだけでよいです。

アルゴリズム

1. 全商品の合計金額 \(S\) を求める
2. \(S\) に適用される最大のティアを求める
   • つまり、\(T_i \leq S\) を満たす最大の \(i\) を探す
   • これは \(T\) が昇順なので二分探索で求められる
3. 割引額 $\( \left\lfloor \frac{S \times P_i}{100} \right\rfloor \)$ を計算する
4. 答えは $\( S - \left\lfloor \frac{S \times P_i}{100} \right\rfloor \)$

---

例えば、商品合計が \(S=1200\) 円で、

• \(T_1=0, P_1=0\)
• \(T_2=1000, P_2=10\)

なら、全てスーパーで買えば割引額は

\[ \left\lfloor 1200 \times 10 / 100 \right\rfloor = 120 \]

で、支払額は \(1080\) 円です。

一方、もし \(800\) 円分だけスーパーで買うと割引率は \(0\%\) なので、割引額は \(0\) 円です。
このように、買う金額を減らして得することはありません。

計算量

• 時間計算量: \(O(N + K)\)
• 空間計算量: \(O(K)\)

実装のポイント

• ティアの判定には bisect_right を使うと簡潔に書けます。

  • bisect_right(T, total) - 1 で、\(T_i \leq total\) を満たす最大の \(i\) が求まります。

• 合計金額は最大で $\( N \times 10^9 \leq 2 \times 10^{14} \)$ になるので、言語によっては 64bit 整数が必要です。

• Python では整数が自動で多倍長になるため、そのままで問題ありません。

  ソースコード

import sys
from bisect import bisect_right

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    N = next(it)
    K = next(it)

    T = [0] * K
    P = [0] * K
    for i in range(K):
        T[i] = next(it)
        P[i] = next(it)

    total = 0
    for _ in range(N):
        total += next(it)

    idx = bisect_right(T, total) - 1
    discount = total * P[idx] // 100
    print(total - discount)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.4-high によって生成されました。