整備する遊歩道の区間 \(l,l+1,\dots,r\) のうち、 \(l\) を固定することを考えます。

全ての \(i\) について \(P_i > 0\) なので、総コストが \(B\) 以下である中で \(r\) をより大きく取ることが最適です。
このことから、 尺取り法 を用いてこの問題に正解できます。

• 最初、コスト \(c=0\) 、満足度 \(p=P_1\) と初期化する。また、変数 \(r=1\) とする。
• \(l=1,2,\dots,N-1\) について、以下を繰り返す。
  • 以下を \(r<N\) かつ \(c+C_r \le B\) である限り繰り返す。
    • 遊歩道 \(r\) を整備することにする。
    • \(c\) に \(C_r\) 加算する。
    • \(r\) に \(1\) 加算する。
    • \(p\) に \(P_r\) 加算する。
  • 遊歩道 \(l\) を左端とする整備のうち、達成可能な最大の満足度が \(p\) であると分かる。
  • 遊歩道 \(l\) を整備しないことにする。
  • \(c\) から \(C_l\) 減算する。
  • \(p\) から \(P_l\) 減算する。

全体で時間計算量 \(O(N)\) でこの問題に正解できます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int main(){
  ll N,B;
  cin >> N >> B;
  vector<ll> P(N+1);
  for(ll i=1;i<=N;i++){
    cin >> P[i];
  }
  vector<ll> C(N);
  for(ll i=1;i<N;i++){
    cin >> C[i];
  }

  ll res=P[1],cur=P[1];
  ll r=1;
  for(ll l=1;l<N;l++){
    while(r<N && B-C[r]>=0){
      B-=C[r];
      r++;
      cur+=P[r];
    }
    res=max(res,cur);
    cur-=P[l];
    B+=C[l];
  }
  cout << res << "\n";
  return 0;
}