Overview

We want to create a walking course by developing consecutive promenades, and find the maximum satisfaction achievable within a given budget.

Analysis

In this problem, we select an interval \([l, r]\), develop the promenades in that range, and gain the satisfaction from spots \(l\) to \(r+1\). The total development cost must be at most the budget \(B\).

A brute-force approach would have \(O(N^2)\) combinations, and since \(N\) can be up to \(5 \times 10^5\), this is not practical (it would result in TLE). Therefore, we need to consider a more efficient method.

The key observation is that by using prefix sums of costs and prefix sums of satisfaction, we can quickly compute the cost and satisfaction of any interval. Furthermore, when the cost exceeds the budget, we can move the left endpoint to the right to maintain a valid range while updating the maximum satisfaction — this is the “two-pointer (sliding window) technique.”

In other words, while fixing the right endpoint \(r\), we move the left endpoint \(l\) so that the cost stays within the budget, computing the satisfaction each time and updating the maximum.

Algorithm

1. Precompute prefix sums of the spot scores \(P\) and the promenade costs \(C\).
2. Apply the two-pointer technique, repeating the following:
   • While incrementing the right endpoint \(r\) by 1, check the cost of the interval \([l, r]\): \(C\_sum[r] - C\_sum[l-1]\).
   • If the cost exceeds the budget \(B\), advance the left endpoint \(l\).
   • For each valid interval, compute the corresponding satisfaction \(P\_sum[r+1] - P\_sum[l-1]\) and update the maximum.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Be careful with prefix sum index management (aligning to 1-based indexing makes it easier to understand)

• In the two-pointer technique, fix the right pointer and move the left pointer as needed

• Initialize the maximum value to 0

  Source Code

import sys
from itertools import accumulate

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    B = int(data[1])
    P = list(map(int, data[2:2+N]))
    C = list(map(int, data[2+N:2+N+N-1]))
    
    # 累積和を計算
    P_sum = [0] + list(accumulate(P))
    C_sum = [0] + list(accumulate(C))
    
    max_satisfaction = 0
    left = 1
    for right in range(1, N):
        # コストが予算を超える場合はleftを進める
        while C_sum[right] - C_sum[left-1] > B:
            left += 1
        # 満足度を計算
        satisfaction = P_sum[right+1] - P_sum[left-1]
        if satisfaction > max_satisfaction:
            max_satisfaction = satisfaction
    
    print(max_satisfaction)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.