F - More Holidays Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

o と x からなる長さ N の文字列 S と、整数 M,K が与えられます。
S には少なくとも 1 つの x が含まれることが保証されます。

S を M 個連結して得られる長さ NM の文字列を T とします。 T に含まれる x のうち丁度 K 個を選んで o に変えることを考えます。
あなたの目標は、変更後の T に o のみからなるできるだけ長い連続部分文字列が含まれるようにすることです。
o のみからなる連続部分文字列の長さとして達成可能な最大値を求めてください。

制約

  • N,M,K は整数
  • 1 \le N \le 3 \times 10^5
  • 1 \le M \le 10^9
  • x を文字列 T に含まれる x の総数としたとき、 1 \le K \le x
  • S は o と x からなる長さ N の文字列
  • S には少なくとも 1 つの x が含まれる

入力

入力は以下の形式で標準入力から与えられる。

N M K
S

出力

答えを整数として出力せよ。

入力例 1

10 1 2
ooxxooooox

出力例 1

9

S= ooxxooooox 、 T= ooxxooooox です。
3 文字目と 4 文字目の x を o に変更することにより、変更後の T= ooooooooox となります。
このとき o のみからなる長さ 9 の連続部分文字列が得られ、これが達成可能な最大値です。

入力例 2

5 3 4
oxxox

出力例 2

8

S= oxxox 、 T= oxxoxoxxoxoxxox です。
5,7,8,10 文字目の x を o に変更することにより、変更後の T= oxxooooooooxxox となります。
このとき o のみからなる長さ 8 の連続部分文字列が得られ、これが達成可能な最大値です。

入力例 3

30 1000000000 9982443530
oxoxooxoxoxooxoxooxxxoxxxooxox

出力例 3

19964887064

Score : 500 points

Problem Statement

You are given a string S of length N consisting of o and x, and integers M and K.
S is guaranteed to contain at least one x.

Let T be the string of length NM obtained by concatenating M copies of S. Consider replacing exactly K x's in T with o.
Your objective is to have as long a contiguous substring consisting of o as possible in the resulting T.
Find the maximum length of a contiguous substring consisting of o that you can obtain.

Constraints

  • N, M, and K are integers.
  • 1 \le N \le 3 \times 10^5
  • 1 \le M \le 10^9
  • 1 \le K \le x, where x is the number of x's in the string T.
  • S is a string of length N consisting of o and x.
  • S has at least one x.

Input

The input is given from Standard Input in the following format:

N M K
S

Output

Print the answer as an integer.

Sample Input 1

10 1 2
ooxxooooox

Sample Output 1

9

S= ooxxooooox and T= ooxxooooox.
Replacing x at the third and fourth characters with o makes T= ooooooooox.
Now we have a length-9 contiguous substring consisting of o, which is the longest possible.

Sample Input 2

5 3 4
oxxox

Sample Output 2

8

S= oxxox and T= oxxoxoxxoxoxxox.
Replacing x at the 5,7,8 and 10-th characters with o makes T= oxxooooooooxxox.
Now we have a length-8 contiguous substring consisting of o, which is the longest possible.

Sample Input 3

30 1000000000 9982443530
oxoxooxoxoxooxoxooxxxoxxxooxox

Sample Output 3

19964887064