T5 小田切蛋糕

题目传送门

思路：

先写好暴力解,通过分别枚举水平切和垂直切,选出所有符合要求的切法。

为了快速判断是否符合要求,可以用前缀和。

枚举时前缀和数组具有二分性,所以可以使用二分进行优化。

样例

5 4 4 2 
1 2 2 1 
3 1 1 1 
2 0 1 3 
1 1 1 1 
1 1 1 1

输出

3

解释

如下图这样切：

1 2 | 2 1  
---------  
3 | 1 1 1  
---------  
2 0 1 | 3  
---------  
1 1 | 1 1  
1 1 | 1 1

这样，小田能获得3块巧克力碎屑。

错误点

• 用错数据；
• 二维前缀和写错；
• 二分查找写错；

学习二分链接

点这里