#P1764. [Baltic2009]monument

    ID: 786 传统题 1000ms 64MiB 尝试: 185 已通过: 105 难度: 7 上传者: 标签>CF2200提高+/省选-网格 DP直方图最大矩形单调栈最近更大/更小元素thanksto

[Baltic2009]monument

题目描述

给一个 p×q×rp\times q\times r 的立方体,它由 p×q×rp\times q\times r 个 1×1×11\times 1\times 1 的小立方体构成。每个立方体要么被虫蛀,要么不被。现在郑爽要选出一个 a×a×ba\times a\times b 的立方体,使得它没有被虫蛀过,并且 4×a×b4\times a\times b 最大。

输入格式

第一行是 p,q,rp,q,r。

以下 p×qp\times q 行,每行 rr 个字符,(x,y,z)(x,y,z)这个格子出现在输入的第 1+(y×p+x−p)1 + (y \times p + x - p)行的第 zz 个字符。N 代表未被虫蛀,P 代表被虫蛀了。

输出格式

仅一行,代表郑爽需要的最大的 4×a×b4\times a\times b。

样例

3 2 5
PNNNN
PNNNN
NPPNP
PNNNP
NNNNP
PPNNP
24

数据规模与约定

对于 100%100\% 的数据:p,q,r≤150p,q,r\leq 150。

题目来源

Baltic2009