概要

価格合計が \(K\) 以下になる 連続区間 を選び、その区間の満足度合計 \(A\) を最大化する問題です。
条件を満たす区間を効率よく探索するために しゃくとり法（スライディングウィンドウ） を使います。

考察

重要な気づき

• 区間 \([l, r]\) の価格合計 \(B_l+\cdots+B_r\) が制約 \(K\) 以下である必要があります。
• ここで \(B_i \ge 1\)（正の値） であることが非常に重要です。
  右端 \(r\) を増やすと価格合計は必ず増え、左端 \(l\) を増やすと価格合計は必ず減ります。

この単調性により、「右端を伸ばして条件を破ったら左端を縮めて戻す」という操作が可能になります。

素朴なアプローチがダメな理由

全ての区間 \((l, r)\) を試すと、区間数は \(O(N^2)\) 個あります。
\(N \le 2\times 10^5\) なので、\(O(N^2)\) は約 \(4\times 10^{10}\) となり、実行時間制限に間に合いません（TLE）。

どう解決するか

• 右端 \(r\) を左から順に動かしつつ、区間 \([l, r]\) を管理する
• 価格合計が \(K\) を超えたら、左端 \(l\) を進めて価格合計を減らす
• その時点で条件を満たす区間について満足度合計の最大値を更新する

この方法なら、各要素は「右端として1回追加」「左端として1回削除」されるだけなので全体で \(O(N)\) になります。

（小さな例） - \(B\) の合計が大きくなりすぎたら左から削ると、必ず合計は減る（\(B_i>0\) だから） - よって「条件を満たす最大区間」を右端ごとに効率よく作れます

アルゴリズム

しゃくとり法で区間 \([l, r]\) を管理し、以下を維持します： - sumB：現在の区間の価格合計 - sumA：現在の区間の満足度合計

手順： 1. 初期状態として \(l=0\), sumA=0, sumB=0, ans=0。 2. \(r=0\) から \(N-1\) まで順に右端を進める： - sumA += A[r], sumB += B[r] として区間に追加 - sumB > K の間、左端を動かして縮める： - sumA -= A[l], sumB -= B[l], l += 1 - 条件 sumB <= K を満たしているので、ans = max(ans, sumA) を更新 3. ans を出力する（条件を満たす区間が無い場合も ans=0 のままなのでOK）

ポイント： - 右端 \(r\) は \(0 \to N-1\) へ一方向にしか進まない - 左端 \(l\) も一方向にしか進まない
よって全体で線形回数の更新で済みます。

計算量

• 時間計算量: \(O(N)\)
  （\(l\) と \(r\) はそれぞれ最大 \(N\) 回しか増えない）
• 空間計算量: \(O(N)\)
  （入力配列 \(A, B\) を保持。保持しない実装にすれば \(O(1)\) も可能）

実装のポイント

• K は最大 \(10^{14}\) なので、価格合計 sumB は 64bit 整数相当で扱う必要があります（Python なら自動でOK）。

• while sumB > K の縮小処理で、区間が必ず条件を満たす状態に戻るまで左端を進めます。

• 条件を満たす区間が1つもない場合でも、ans を \(0\) で初期化しておけば正しく出力できます。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for i in range(N):
        a, b = map(int, input().split())
        A[i] = a
        B[i] = b

    l = 0
    sumA = 0
    sumB = 0
    ans = 0

    for r in range(N):
        sumA += A[r]
        sumB += B[r]
        while l <= r and sumB > K:
            sumA -= A[l]
            sumB -= B[l]
            l += 1
        if sumB <= K:
            if sumA > ans:
                ans = sumA

    print(ans)

if __name__ == "__main__":
    main()

---

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