CF1804D Accommodation

Annie 是一名业余摄影师。她喜欢在夜晚拍摄巨大的居民楼。她刚刚拍摄了一张巨大的矩形建筑的照片，这栋建筑可以看作一个 $n \times m$ 的窗口矩阵。也就是说，这栋楼有 $n$ 层，每层恰好有 $m$ 个窗户。每个窗户要么是黑暗的，要么是明亮的，表示其后房间的灯是否亮着。 Annie 知道，这栋楼里的每套公寓要么是一居室，要么是两居室。每套一居室公寓在照片上恰好对应一个窗户，每套两居室公寓在同一层上恰好对应两个相邻的窗户。此外，保证 $m$ 能被 $4$ 整除，并且已知每层恰好有 $\frac{m}{4}$ 套两居室公寓和 $\frac{m}{2}$ 套一居室公寓。每层的实际公寓布局未知，且每层可能不同。 Annie 认为，如果一套公寓的至少一个窗户是明亮的，那么这套公寓就是“有人居住”的。现在她想知道，根据这张照片，判断“有人居住”的公寓数量的最小值和最大值分别是多少？ 更正式地说，对于每一层，她可以自行设定一种公寓布局，使得恰好有 $\frac{m}{4}$ 套两居室公寓（两个相邻的窗户）和 $\frac{m}{2}$ 套一居室公寓（单独一个窗户）。然后，她统计所有至少有一个明亮窗户的公寓总数。她想知道，这个数的最小值和最大值分别是多少？

输入的第一行包含两个正整数 $n$ 和 $m$（$1 \leq n \cdot m \leq 5 \times 10^5$），分别表示楼层数和每层的窗户数。保证 $m$ 能被 $4$ 整除。 接下来有 $n$ 行，每行包含 $m$ 个字符。第 $i$ 行的第 $j$ 个字符为 "0" 表示第 $i$ 层第 $j$ 个窗户是黑暗的，为 "1" 表示该窗户是明亮的。

输出两个整数，分别表示在每层可以单独选择 $\frac{m}{4}$ 套两居室和 $\frac{m}{2}$ 套一居室公寓布局的情况下，可能的“有人居住”公寓数量的最小值和最大值。

在第一个样例中，每层由一套两居室和两套一居室公寓组成。 如下的公寓布局可以实现最小的“有人居住”公寓数量 $7$： ```

|0 1|0|0|

|1 1|0|0|

|0|1 1|0|

|1|0 1|0|

|1|0|1 1|


```

如下的公寓布局可以实现最大的“有人居住”公寓数量 $10$：

```


|0 1|0|0|

|1|1 0|0|

|0 1|1|0|

|1|0 1|0|

|1 0|1|1|


```

由 ChatGPT 4.1 翻译