Skip to content

1459: 小V的蓝海

题目

题目描述

小V是jjz,他在为小J打call

小J的应援色是蓝色,为了得到更好的效果,小V打算设计一片矩形的蓝海,在活动现场为小J打call。

但由于小J的粉丝 没有稳定的组织,他们在活动场里的分布不一定 能很好的进行应援。

小V设计的应援方式如下: 粉丝们使用大型应援牌进行应援, 应援牌占用 h*w 大小的位置,可以横着也可以竖着,但是不能被分割,同一个位置的粉丝可以举多个应援牌(即应援牌之间可以重叠,但区域不能完全相同)。

现在,小V已经提前拿到了粉丝们的座位分布(由一个矩形表示,具体请看输入格式),他想知道,在现有的分布下,小V能得到多大的蓝海为小J打call(蓝海大小以应援牌的个数表示,具体请参考样例)

小V不想人工去手算,所以他想请你写个程序来帮忙解决这个问题。

输入格式

第一行是四个整数 n,m,h,w 表示观众席的大小为 n*m, 应援牌的高和宽h和w

接下来 n 行 m 列,输入一个只有 0 或 1 的矩阵,表示一个座位上是否有小J的粉丝(0表示有,1表示没有)

样例输入

6 6 2 3

0 0 0 1 0 0

0 1 0 0 0 0

0 0 0 0 0 1

0 0 0 0 0 1

0 0 0 0 0 0

0 0 0 1 0 0

样例输出

16

数据范围

20%的数据,n=2,m=3

100%的数据,n<=150,m<=10

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!