103005: [Atcoder]ABC300 F - More Holidays

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:7 Solved:0

Description

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

Input

题意翻译

给你一个由 `o` 和 `x` 组成的长度为 $N$ 的字符串 $S$,以及整数 $M$ 和 $K$。保证 $S$ 至少包含一个 `x`。 假设 $T$ 是由 $S$ 复制 $M$ 次而成的长度为 $NM$ 的字符串。考虑将 $T$ 中的 $K$ 个 `x` 恰好替换为 `o`。 你的目标是在替换后的 $T$ 中有尽可能长的由 `o` 组成的连续子串。 找出在替换后由 `o` 组成的连续子串的最大长度。

Output

分数:500分

问题描述

给你一个长度为$N$的字符串$S$,由字符ox组成,以及整数$M$和$K$。
$S$中至少包含一个x

将$S$重复$M$次得到字符串$T$,长度为$NM$。考虑将$T$中的$K$个x替换为o
你的目标是在最终的$T$中拥有尽可能长的连续子串o
找出你可以得到的最长连续子串o的长度。

约束

  • $N$、$M$和$K$是整数。
  • $1 \le N \le 3 \times 10^5$
  • $1 \le M \le 10^9$
  • $1 \le K \le x$,其中$x$是字符串$T$中x的数量。
  • $S$是一个长度为$N$的字符串,由字符ox组成。
  • $S$中至少包含一个x

输入

输入从标准输入中给出,格式如下:

$N$ $M$ $K$
$S$

输出

打印一个整数作为答案。


样例输入1

10 1 2
ooxxooooox

样例输出1

9

$S=$ ooxxooooox,$T=$ ooxxooooox
将第三个和第四个字符的x替换为o得到$T=$ ooooooooox
现在我们有了一个长度为$9$的连续子串o,这是可能的最长长度。


样例输入2

5 3 4
oxxox

样例输出2

8

$S=$ oxxox,$T=$ oxxoxoxxoxoxxox
将第$5,7,8$和$10$个字符的x替换为o得到$T=$ oxxooooooooxxox
现在我们有了一个长度为$8$的连续子串o,这是可能的最长长度。


样例输入3

30 1000000000 9982443530
oxoxooxoxoxooxoxooxxxoxxxooxox

样例输出3

19964887064

HINT

长度为n的ox串,可以先复制m次,允许替换k个x为o,最长的连续o子串长度是多少?

加入题单

上一题 下一题 算法标签: