Overview

Choose one contiguous interval of length \(K\) and find the maximum number of sunny days (S) contained in that interval.

Analysis

We need to count the “number of sunny days” for each interval (from day \(d\) to day \(d+K-1\)) and take the maximum. There are \(N-K+1\) intervals in total.

• Naive approach: Recount all \(K\) days for each interval
  → The complexity becomes \(O((N-K+1)\times K) \approx O(NK)\), which for \(N,K \le 10^6\) results in up to around \(10^{12}\) operations and won’t finish in time (TLE).

The key observation here is that adjacent intervals overlap almost entirely.

Example: When \(K=3\)
- After interval \([1,3]\) comes \([2,4]\)
→ The common part is \([2,3]\), so the only change is “one day leaving” and “one day entering”.
In other words, there’s no need to recount all \(K\) elements each time — we can perform a difference update from the previous interval’s result.

Algorithm

We solve this using a sliding window (a classic two-pointer technique).

1. For each day, create an array arr where sunny days are converted to \(1\) and all others (C, R) to \(0\).
2. Compute the sum s of the first \(K\) days (\([0, K-1]\)) and set this as the tentative maximum best.
3. Slide the interval one day to the right at a time, repeating the following (\(i = K, K+1, ..., N-1\)):
   • Add the newly entering day arr[i]
   • Subtract the day leaving from the left end arr[i-K]
     That is, s += arr[i] - arr[i-K]
   • Update best = max(best, s)
4. Output best.

This method is fast because each day is processed only a constant number of times.

Complexity

• Time complexity: \(O(N)\)
  (The initial sum computation is \(O(K)\) and the sliding updates are \(O(N-K)\), which totals to \(O(N)\))
• Space complexity: \(O(N)\)
  (For the array arr that stores whether each day is sunny as 0/1)

Implementation Notes

• Since \(N \le 10^6\), input can become a bottleneck in Python. The submitted code reads all input at once using sys.stdin.buffer.read() and parses it efficiently by skipping whitespace.

• The weather is a string, but since we only need to know whether it’s S or not, we compare 'S' with byte value 83 and convert to 1/0 (arr[i] = 1 if c == 83 else 0).

• In the sliding window, it’s important not to mix up “adding the entering element” and “subtracting the leaving element” (arr[i] - arr[i-K]).

  Source Code

import sys

data = sys.stdin.buffer.read()
L = len(data)
p = 0

def skip():
    global p
    while p < L and data[p] <= 32:
        p += 1

def read_int():
    global p
    skip()
    x = 0
    while p < L and data[p] > 32:
        x = x * 10 + (data[p] - 48)
        p += 1
    return x

N = read_int()
K = read_int()

arr = bytearray(N)
for i in range(N):
    skip()
    c = data[p]
    arr[i] = 1 if c == 83 else 0  # 'S' == 83
    p += 1
    while p < L and data[p] > 32:
        p += 1

s = 0
for i in range(K):
    s += arr[i]
best = s

for i in range(K, N):
    s += arr[i] - arr[i - K]
    if s > best:
        best = s

sys.stdout.write(str(best))

This editorial was generated by gpt-5.2-high.