Overview

This problem asks us to maximize the total score (satisfaction) of spots visited when maintaining a contiguous sequence of trails, subject to a budget of \(B\) or less. It can be efficiently solved using the classic “Two Pointers” technique (also known as the sliding window method).

Analysis

Rephrasing the Problem

When we select an interval \((l, r)\): - Cost: \(C_l + C_{l+1} + \cdots + C_r\) - Satisfaction: \(P_l + P_{l+1} + \cdots + P_{r+1}\)

In other words, we select a contiguous subsequence of trails and maximize satisfaction while keeping the cost at most \(B\).

Naive Approach

Trying all pairs \((l, r)\) gives \(O(N^2)\) combinations, and computing the sum for each pair takes \(O(N^3)\) in the worst case (\(O(N^2)\) with prefix sums). Since \(N \leq 5 \times 10^5\), even \(O(N^2)\) is too slow.

Key Observation

• All costs \(C_i\) are positive values.
• Therefore, when \(l\) is fixed, the cost increases monotonically as \(r\) increases.
• When \(l\) is shifted one position to the right, the leftmost cost \(C_l\) is removed, reducing the total cost and potentially allowing \(r\) to extend further to the right.

Thanks to this monotonicity, the two pointers technique can be applied.

Algorithm

We use the Two Pointers technique.

1. Move the left endpoint \(l\) from \(0\) to \(N-2\) in order (0-indexed).
2. For each \(l\), extend the right endpoint \(r\) as far right as possible while the cost remains at most \(B\).
3. When \(r \geq l\) (i.e., at least one trail is maintained), update the answer with the current satisfaction.
4. When shifting \(l\) one position to the right, subtract \(C_l\) from the cost and \(P_l\) from the satisfaction.

Concrete example (\(N=5, B=5\)):

Spots:   P = [3, 1, 4, 1, 5]
Trails:  C = [2, 3, 1, 4]

\(l\)	\(r\)	Cost	Cost sum	Remarks
0	2	\(2+3+1=6 > 5\) → \(r=1\)	\(2+3=5\)	\(P_0+P_1+P_2=3+1+4=8\)
1	2	\(3+1=4 \leq 5\)	\(3+1=4\)	\(P_1+P_2+P_3=1+4+1=6\)
1	2	\(r=3\) gives \(4+4=8>5\)	—	\(r\) stays at \(2\)

Since \(r\) never moves backward even as \(l\) moves to the right, the pointers move a total of \(O(N)\) times overall.

Complexity

• Time complexity: \(O(N)\)
  • Each of \(l\) and \(r\) advances at most \(N\) times, so the total is \(O(N)\).
• Space complexity: \(O(N)\)
  • \(O(N)\) is needed to store the arrays \(P\) and \(C\).

Implementation Notes

• Initial state management: Start with \(r = l - 1\) (no trail selected yet), sat_sum = P[l], and cost_sum = 0. Each time \(r\) is advanced by one, add \(C[r]\) and \(P[r+1]\) to the running sums.

• Checking \(r \geq l\): Only update the answer when at least one trail is being maintained. Since the constraints guarantee \(C_i \leq B\), for each \(l\), choosing \(r = l\) is always feasible.

• Overflow prevention: Since \(P_j\) can be up to \(10^9\) and \(N\) can be up to \(5 \times 10^5\), the maximum possible satisfaction sum is approximately \(5 \times 10^{14}\). In Python, integer overflow is not an issue, but in other languages, 64-bit integers must be used.

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    B = int(input_data[idx]); idx += 1
    
    P = [int(input_data[idx + i]) for i in range(N)]
    idx += N
    C = [int(input_data[idx + i]) for i in range(N - 1)]
    idx += N - 1
    
    # We need to find l, r (1-indexed, 1 <= l <= r <= N-1) such that
    # sum of C[l..r] <= B and sum of P[l..r+1] is maximized.
    # Using 0-indexed: l in [0, N-2], r in [l, N-2]
    # cost = C[l] + ... + C[r]
    # satisfaction = P[l] + P[l+1] + ... + P[r+1]
    
    # Two pointer / sliding window approach
    # We expand r to the right as long as cost <= B, tracking max satisfaction.
    
    # Prefix sums for P and C
    # P_prefix[i] = P[0] + ... + P[i-1]
    # C_prefix[i] = C[0] + ... + C[i-1]
    
    best = -1
    cost_sum = 0
    sat_sum = 0
    
    # l and r are 0-indexed indices into C (0 to N-2)
    # satisfaction for (l, r) = P[l] + P[l+1] + ... + P[r+1]
    # cost for (l, r) = C[l] + C[l+1] + ... + C[r]
    
    l = 0
    # Initialize with l=0, r=0
    # We'll use a sliding window
    
    # sat_sum will track P[l] + ... + P[r+1]
    # cost_sum will track C[l] + ... + C[r]
    
    # Start: l=0, r not yet set. We'll iterate r from 0 to N-2.
    
    sat_sum = P[0]  # P[l] initially, before adding r
    cost_sum = 0
    
    # Actually let me redo this more carefully with two pointers.
    # For each l, find the maximum r such that cost <= B.
    # As l increases, the maximum r can only increase or stay the same.
    
    # We maintain sat_sum = P[l] + ... + P[r+1] and cost_sum = C[l] + ... + C[r]
    # Start with l=0, r=-1 (no road selected yet), sat_sum = P[0], cost_sum = 0
    
    r = -1  # r hasn't been set yet; means no road selected
    sat_sum = P[0]
    cost_sum = 0
    
    for l in range(N - 1):
        # Ensure r >= l
        if r < l:
            r = l - 1
            # Reset: sat_sum should be P[l], cost_sum should be 0
            # But we need to handle this carefully
            # When r = l-1, we haven't selected any road yet for this l
            sat_sum = P[l]
            cost_sum = 0
        
        # Expand r as far as possible
        while r + 1 <= N - 2 and cost_sum + C[r + 1] <= B:
            r += 1
            cost_sum += C[r]
            sat_sum += P[r + 1]
        
        # Now r is the maximum valid r for this l (r >= l - 1)
        # But we need r >= l for a valid selection
        if r >= l:
            if sat_sum > best:
                best = sat_sum
        
        # Move l forward: remove C[l] from cost and P[l] from satisfaction
        if r >= l:
            cost_sum -= C[l]
            sat_sum -= P[l]
        else:
            # r < l means we couldn't even select road l, which contradicts
            # the constraint that C[i] <= B. So this shouldn't happen.
            # But just in case:
            sat_sum = P[l + 1]
            cost_sum = 0
    
    print(best)

main()

---

This editorial was generated by claude4.6opus-thinking.