103005: [Atcoder]ABC300 F - More Holidays
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 obo
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
andx
. - $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$,由字符o
和x
组成,以及整数$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$的字符串,由字符
o
和x
组成。 - $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