[Aya Round 1 G] 咕噜论坛(post)

Luogu
IDLGP8472
Time2000ms
Memory512MB
DifficultyP4
洛谷原创Special JudgeO2优化洛谷月赛双指针 two-pointer
「咕噜论坛」的一篇帖子下,有若干个不同的人对其进行了回复,这些评论形成了一个 $n\times m$ 的矩阵。 论坛管理员 prAB 发现这些评论者的名字颜色只有灰名、紫名和棕名三种,他决定「动用神权」来增加这些评论的整齐度。但是论坛站长超氧化铯(CsO2)可能会因为他「滥用神权」导致论坛「臭名昭著」而踢掉他的管理身份。所以 prAB **最多**只能动用 $k$ 次神权。已知他的神权有两种: - 「暴政警告」:送一个灰名进陶片使他变成棕名。 - 「放人一马」:将一个棕名解封使他变成灰名。 由于「咕噜论坛」的管理员是至高无上的,对于评论中的紫名他无能为力。 prAB 认为在这些评论者的名字颜色中,最大的颜色相同的子矩阵的大小能代表这篇帖子评论的整齐度。所以他想知道,他动用完神权后评论的整齐度的最大值。 ## Input - 第一行输入三个整数 $n,m,k$。 - 接下来 $n$ 行,每行输入一个长度为 $m$ 的字符串,代表评论矩阵中每个人名字的颜色。其中 `B` 代表棕名,`G` 代表灰名,`P` 代表紫名。 ## Output - 第一行输出一个整数,表示整齐度的最大值。 - 下面 $n$ 行,每行输出一个长度为 $m$ 的字符串,格式同「输入格式」。代表修改完后每个人名字的颜色。如有多种方案输出则任意一种即可。 [samples] ## Note ### 数据范围及约定 对于 $100\%$ 的数据,$1 \le n,m\le 500$,$0 \le k \le nm$。字符矩阵中只会出现大写字母 `B`、`G` 和 `P`。
Samples
Input #1
3 4 2
BBGB
GBBB
PGPP
Output #1
8
BBBB
BBBB
PGPP
API Response (JSON)
{
  "problem": {
    "name": "[Aya Round 1 G] 咕噜论坛(post)",
    "description": {
      "content": "「咕噜论坛」的一篇帖子下,有若干个不同的人对其进行了回复,这些评论形成了一个 $n\\times m$ 的矩阵。 论坛管理员 prAB 发现这些评论者的名字颜色只有灰名、紫名和棕名三种,他决定「动用神权」来增加这些评论的整齐度。但是论坛站长超氧化铯(CsO2)可能会因为他「滥用神权」导致论坛「臭名昭著」而踢掉他的管理身份。所以 prAB **最多**只能动用 $k$ 次神权。已知他的神权有两种: ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8472"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "「咕噜论坛」的一篇帖子下,有若干个不同的人对其进行了回复,这些评论形成了一个 $n\\times m$ 的矩阵。\n\n论坛管理员 prAB 发现这些评论者的名字颜色只有灰名、紫名和棕名三种,他决定「动用神权」来增加这些评论的整齐度。但是论坛站长超氧化铯(CsO2)可能会因为他「滥用神权」导致论坛「臭名昭著」而踢掉他的管理身份。所以 prAB **最多**只能动用 $k$ 次神权。已知他的神权有两种:\n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments