概要

標高が \(X\) 未満の休憩スポットからいくつか選び、訪問順の標高が厳密に減少するように並べたときの景観スコア合計の最大値を求めます。結論として「条件を満たすスポットのうち、スコアが正のものを全部取る」のが最適です。

考察

この問題のポイントは、訪問順を自由に決められることです。

• 条件1：立ち寄る各スポットは \(A_i < X\) でなければならない
  → まず候補は「標高が \(X\) より低いスポット」に限定されます。

• 条件2：訪問順で標高が厳密に減少
  → ここが一見ややこしく見えますが、選んだスポットを標高の高い順に並べれば必ず条件を満たします。
  なぜなら \(A_i\) はすべて異なるので、降順に並べると \(A_{p1} > A_{p2} > \dots\) と必ず厳密不等号になります。

つまり、条件を満たすために「並べ方」で困ることはなく、実質的には

「\(A_i < X\) を満たすスポットから、好きなものを好きなだけ選べる」

のと同じです。

このとき最大化したいのはスコア合計なので、 - \(B_i > 0\) のスポットは入れるほど得 - \(B_i \le 0\) のスポットは入れると損（または得なし）

よって \(A_i < X\) かつ \(B_i > 0\) を満たすすべてのスポットを選ぶのが最適です（訪問しない選択も可能なので負の値は避けられます）。

例：\(X=100\)、候補スポットが
- \((A,B)=(90, +5),(80,-3),(70,+10)\)
なら、標高は自由に降順 \((90 \to 80 \to 70)\) にできますが、\(-3\) は入れない方が良いので、答えは \(5+10=15\) です。

素朴に「最適な下降列」をDPで探したり、LISのような問題だと誤解して \(O(N\log N)\) や \(O(N^2)\) を組む必要はありません（そもそも順序を自由に決められるため、その種のDPは本質ではありません）。

アルゴリズム

1. 初期値 \(ans=0\) とする。
2. 各スポット \((A_i, B_i)\) について、
   • もし \(A_i < X\) かつ \(B_i > 0\) なら \(ans \leftarrow ans + B_i\)
3. \(ans\) を出力する。

これで「条件を満たすスポットのうち、利益になるものだけ全部取る」を実現できます。

計算量

• 時間計算量: \(O(N)\)（各スポットを1回見るだけ）
• 空間計算量: \(O(1)\)（入力を逐次処理し、追加の配列を持たない）

実装のポイント

• \(N\) が最大 \(2\times 10^5\) なので、Pythonでは sys.stdin.buffer.read() による高速入力が安全です。

• 負のスコアや \(A_i \ge X\) を確実に除外するため、条件は if A < X and B > 0: のようにそのまま書くのが分かりやすいです。

  ソースコード

import sys

def main():
    it = iter(sys.stdin.buffer.read().split())
    N = int(next(it))
    X = int(next(it))
    ans = 0
    for _ in range(N):
        A = int(next(it))
        B = int(next(it))
        if A < X and B > 0:
            ans += B
    print(ans)

if __name__ == "__main__":
    main()

---

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