1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import sys

input = sys.stdin.readline
n, k, t = map(int, input().split())
duties = input().strip()

assert len(duties) == n
sums = [[0] * 4 for _ in range(n + 1)]
for i in range(1, n + 1):
  sums[i][1] = sums[i - 1][1] + (duties[i - 1] == "1")
  sums[i][2] = sums[i - 1][2] + (duties[i - 1] == "2")
  sums[i][3] = sums[i - 1][3] + (duties[i - 1] == "3")


result = -1
total_office_meetings = sums[n][1] - sums[0][1]
total_remote_meetings = sums[n][2] - sums[0][2]
# no office visit
if total_office_meetings <= k:
  can_skip_remote = min(total_remote_meetings, k - total_office_meetings)
  # print(f"{total_office_meetings=} {total_remote_meetings=} {can_skip_remote=}")
  result = sums[n][3] - sums[0][3] + can_skip_remote + total_office_meetings

for office_start in range(1, n - t + 1):
  for office_end in range(office_start + t, n - t + 2):
    if office_start + n - office_end - t + 1 < result:
      break
    in_office_meetings = sums[office_end - 1][1] - sums[office_start + t - 1][1]
    skipped_in_office_meetings = total_office_meetings - in_office_meetings
    skipped_remote_meetings = (
      sums[office_start + t - 1][2]
      - sums[office_start - 1][2]
      + sums[office_end + t - 1][2]
      - sums[office_end - 1][2]
    )
    # print(
    #   f"{office_start=} {office_end=} {in_office_meetings=} {skipped_in_office_meetings=}, {skipped_remote_meetings=}"
    # )
    if skipped_in_office_meetings + skipped_remote_meetings > k:
      continue

    remaining_remote = (
      -sums[0][2] + sums[office_start - 1][2] - sums[office_end + t - 1][2] + sums[n][2]
    )
    remaining_in_office_meetings = (
      -sums[0][1] + sums[office_start - 1][1] - sums[office_end + t - 1][1] + sums[n][1]
    )
    # print(f"{remaining_in_office_meetings=}")
    can_skip_remote = min(
      remaining_remote,
      k - skipped_in_office_meetings - skipped_remote_meetings,
    )
    result = max(
      result,
      -sums[0][3]
      + sums[office_start - 1][3]
      - sums[office_end + t - 1][3]
      + sums[n][3]
      + can_skip_remote
      + remaining_in_office_meetings,
    )

print(result)