概要

重さの合計が \(K\) 以下になる「連続区間」を選ぶとき、満足度合計 \(\sum A_i\) の最大値を求めます。制約が大きいので、区間を効率よく探索します。

考察

連続区間 \([l, r]\) を選ぶとき、条件は - 重さ合計 \(\sum_{i=l}^{r} B_i \le K\) - 満足度合計 \(\sum_{i=l}^{r} A_i\) を最大化

です。

素朴に全ての区間を調べると、区間数は \(O(N^2)\)（約 \(2 \times 10^5\) なら最大で約 \(2 \times 10^{10}\)）となり、到底間に合いません（TLE）。

ここで重要な観察は次の通りです：

• \(B_i \ge 1\) なので、右端 \(r\) を右に伸ばすと重さ合計は増える（または同じにはならない）。
• ある \(r\) を固定したとき、条件 \(\sum B_i \le K\) を満たすための左端 \(l\) は「必要なら右に動かす」ことで調整でき、\(l\) を左に戻す必要はありません。

つまり、左端と右端をそれぞれポインタとして持ち、「右端を1つ進める → 重すぎたら左端を進めて軽くする」を繰り返せば、全体を一度なめるだけで最大値を更新できます。

（例） - 右端を伸ばして重さが \(K\) を超えたら、左端の本を取り除く（左端を進める）ことで重さを減らし、再び \(\le K\) に戻す。

アルゴリズム

しゃくとり法（Two Pointers / Sliding Window）を使います。

• \(l=0\)（左端）、\(\text{sumA}=0\)（満足度合計）、\(\text{sumB}=0\)（重さ合計）で初期化
• \(r=0,1,\dots,N-1\) と右端を順に進める：
  1. 本 \(r\) を区間に追加：
     \(\text{sumA} \mathrel{+}= A[r],\ \text{sumB} \mathrel{+}= B[r]\)
  2. もし \(\text{sumB} > K\) なら、条件を満たすまで左端を縮める：
     while \(\text{sumB} > K\)：
     • \(\text{sumA} \mathrel{-}= A[l],\ \text{sumB} \mathrel{-}= B[l]\)
     • \(l \mathrel{+}= 1\)
  3. この時点で区間 \([l, r]\) は必ず \(\sum B_i \le K\) を満たすので、答え候補として \(\text{ans} = \max(\text{ans}, \text{sumA})\) を更新

ポイントは、各要素は「右端として1回追加」「左端として1回削除」されるだけなので、全体が線形時間で終わります。

計算量

• 時間計算量: \(O(N)\)（\(l\) も \(r\) も最大で \(N\) 回しか増えない）
• 空間計算量: \(O(N)\)（配列 \(A, B\) を保持する分）

実装のポイント

• \(K\) が最大 \(10^{15}\)、合計も大きくなるため、\(\text{sumA}, \text{sumB}\) は 64bit整数で扱う必要があります（Pythonなら自動でOK）。

• 入力が大きいので、sys.stdin.buffer.read() のような高速入力を使うと安全です。

• 「条件を満たす区間が少なくとも1つある」ので、常に答えは更新可能です（ただし実装では ans=0 で問題ありません）。

  ソースコード

import sys

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    K = next(it)
    A = [next(it) for _ in range(N)]
    B = [next(it) for _ in range(N)]

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

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

    print(ans)

if __name__ == "__main__":
    main()

---

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