Overview

This problem asks us to find the number of ways to cancel a contiguous range of days (or \(0\) days) from an \(N\)-day trip so that the total cost of the trip becomes exactly \(K\) yen. By focusing on the “total cost of the canceled days”, organizing the conditions, and applying the two-pointer technique, this problem can be solved in \(O(N)\) time.

Analysis

1. Rephrasing the Problem

Let the total cost of the entire trip be \(S = \sum_{i=1}^N A_i\). Making the remaining cost exactly \(K\) yen is equivalent to making the total cost of the canceled days exactly \(T = S - K\) yen.

There are two choices for canceling: 1. Canceling no days: The canceled cost is \(0\) yen. 2. Canceling a contiguous range \([l, r]\): The canceled cost is \(\sum_{i=l}^r A_i\) yen.

From the constraints, each day’s cost satisfies \(A_i \ge 1\), so the canceled cost is always at least \(1\) if one or more days are canceled. From this property, we can divide into cases based on the value of \(T\):

• When \(T < 0\): It is impossible to achieve because the canceled cost cannot be negative. The answer is 0.
• When \(T = 0\): Since the canceled cost must be \(0\), the only way is to “cancel no days,” which gives exactly 1 way (canceling any range reduces the cost by at least \(1\) since \(A_i \ge 1\)). The answer is 1.
• When \(T > 0\): The option of “canceling no days” is excluded because its cost is \(0\). Therefore, it suffices to find the number of ranges \([l, r]\) whose contiguous subarray sum is exactly \(T\).

2. Naive Approach and Optimization

A naive approach that calculates the sum for every range \([l, r]\) \((1 \le l \le r \le N)\) takes \(O(N^2)\) time because there are \(\frac{N(N+1)}{2}\) ranges. Given the constraint \(N \le 10^6\), this approach will exceed the time limit (TLE).

Here, we notice that all elements are positive (\(A_i > 0\)). Extending the right end of the range to the right monotonically increases the sum, and shrinking the left end to the right monotonically decreases the sum. Utilizing this monotonicity, we can search in \(O(N)\) using the two-pointer technique.

Algorithm

We count the number of ranges whose contiguous subarray sum is \(T\) using the two-pointer technique.

1. Calculate the total sum \(S\), and find \(T = S - K\).
2. If \(T < 0\), output 0; if \(T = 0\), output 1, and terminate.
3. Initialize the left end of the range left, the right end right, the current range sum cur, and the answer counter ans.
4. Advance right from \(0\) to \(N-1\) in order, performing the following:
   • Add \(A[\text{right}]\) to cur.
   • While cur > T, subtract \(A[\text{left}]\) from cur and increment left by \(1\).
   • If cur == T, we found a range whose sum is \(T\), so increment ans by \(1\).
5. Output the final value of ans.

Complexity

• Time Complexity: \(O(N)\) right advances \(N\) times from \(0\) to \(N-1\). In addition, left advances at most \(N\) times, so the operations inside the loop are executed at most \(2N\) times in total. Therefore, the time complexity is \(O(N)\), which easily runs within the time limit.
• Space Complexity: \(O(N)\) \(O(N)\) memory is used to store the array \(A\).

Implementation Notes

• Since the input size is large with \(N \le 10^6\), in Python, reading the entire input at once using sys.stdin.read can speed up the execution.

• Since \(A_i \ge 1\), for each right, there is at most one left such that the range sum equals \(T\). Therefore, it is completely valid to simply increment ans += 1 when cur == T.

  Source Code

import sys


def main():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return

    N = int(data[0])
    K = int(data[1])
    A = [int(x) for x in data[2:]]

    S = sum(A)
    T = S - K

    if T < 0:
        print(0)
        return
    if T == 0:
        print(1)
        return

    ans = 0
    cur = 0
    left = 0
    for right in range(N):
        cur += A[right]
        while cur > T:
            cur -= A[left]
            left += 1
        if cur == T:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

---

This editorial was generated by gemini-3.8-flash-high.