Overview

Choose a “contiguous trail segment” that can be maintained within budget \(B\), and maximize the total score (satisfaction) of the spots that can be visited within that segment.

Analysis

If we denote the maintained segment as \((l,r)\) (\(1 \le l \le r \le N-1\)), then:

• Cost: \(C_l + C_{l+1} + \cdots + C_r\)
• Satisfaction: \(P_l + P_{l+1} + \cdots + P_{r+1}\) (there is one more spot than trails)

Both are “sums over contiguous segments.”

Why a Naive Solution Doesn’t Work

Trying all \((l,r)\) pairs gives \(O(N^2)\) combinations, and even if we compute each segment sum efficiently, with \(N\) up to \(5\times 10^5\) this will certainly TLE.

Key Observations

• All costs \(C_i\) are positive (\(C_i \ge 1\)), so expanding the segment to the right monotonically increases the cost.
• Therefore, “for a fixed right endpoint, the minimum left endpoint satisfying the condition” can be updated using the two pointers (sliding window) technique.
• Segment sums can be computed in \(O(1)\) using prefix sums.

Combining these two ideas, we can solve the entire problem in \(O(N)\).

Algorithm

We consider 0-indexed arrays (the code does the same).

• Trails: \(C[0], C[1], \dots, C[N-2]\)
• Spots: \(P[0], P[1], \dots, P[N-1]\)

First, build prefix sums:

• Spot prefix sum: \(\text{prefP}[k] = \sum_{i=0}^{k-1} P[i]\) (length \(N+1\))
• Cost prefix sum: \(\text{prefC}[k] = \sum_{i=0}^{k-1} C[i]\) (length \(N\))

If the trail segment is \([l, r]\) (0-indexed, both endpoints inclusive), then:

• Cost is \(\text{prefC}[r+1] - \text{prefC}[l]\)
• Satisfaction (spots from \(l\) to \(r+1\)) is \(\text{prefP}[r+2] - \text{prefP}[l]\)

The two pointers technique proceeds as follows:

1. Set \(l=0\)
2. Move the right endpoint \(r=0,1,\dots,N-2\) in order
3. While the cost \(\text{prefC}[r+1]-\text{prefC}[l] > B\), increment \(l\) to shrink the segment
4. Once the condition is satisfied, update the answer with the satisfaction \(\text{prefP}[r+2]-\text{prefP}[l]\)

Since costs are positive, when \(r\) advances, \(l\) never moves backward, so each pointer moves at most \(N\) times in total.

Complexity

• Time complexity: \(O(N)\) (with the two pointers technique, \(l\) and \(r\) each move at most \(N\) times)
• Space complexity: \(O(N)\) (for the prefix sum arrays)

Implementation Notes

• Be careful with index correspondence: For trail segment \([l,r]\), the spots covered are \([l, r+1]\), so the satisfaction is \(\text{prefP}[r+2]-\text{prefP}[l]\).

• Prefix sum array lengths:

  • \(\text{prefP}\) has length \(N+1\)
  • \(\text{prefC}\) has length \((N-1)+1 = N\)

• Since the constraints are large, in Python using sys.stdin.buffer.read() for fast input is effective (the provided code implements this).

  Source Code

import sys

def ints():
    data = sys.stdin.buffer.read()
    n = len(data)
    i = 0
    while i < n:
        while i < n and data[i] <= 32:
            i += 1
        if i >= n:
            break
        num = 0
        while i < n and data[i] > 32:
            num = num * 10 + (data[i] - 48)
            i += 1
        yield num

it = ints()
N = next(it)
B = next(it)

P = [next(it) for _ in range(N)]
C = [next(it) for _ in range(N - 1)]

prefP = [0] * (N + 1)
for i, v in enumerate(P):
    prefP[i + 1] = prefP[i] + v

prefC = [0] * N  # length (N-1)+1
for i, v in enumerate(C):
    prefC[i + 1] = prefC[i] + v

ans = 0
l = 0
for r in range(N - 1):
    while prefC[r + 1] - prefC[l] > B:
        l += 1
    s = prefP[r + 2] - prefP[l]
    if s > ans:
        ans = s

print(ans)

---

This editorial was generated by gpt-5.2-high.