#P3726. PA2014Final Wykladzina

    ID: 2939 传统题 2000ms 128MiB 尝试: 67 已通过: 22 难度: 7 上传者: 标签>CF2300提高+/省选-有限候选集缩减单调栈最近更大/更小元素线段树上二分鸣谢Jcvb

PA2014Final Wykladzina

题目描述

有一块 w∗sw*s 的地毯,其中有些格子是坏的。从中剪出一块面积尽可能大的子矩形,使得其中至多包含一个坏格。

输入格式

第一行两个整数 w,sw,s(1≤w,s≤2000)(1≤w,s≤2000)。 接下来 ww 行,每行有 ss 个字符,'.' 表示这格是好的,'#' 表示这格是坏的。

输出格式

输出最大面积。

输入样例

4 5
#.#..
....#
..#..
....#

输出样例

12

鸣谢 Jcvb 提供题目。