Nebius Welcome Round (Div. 1 + Div. 2) |
---|
Закончено |
Энни — фотограф-любитель. Ей нравится фотографировать гигантские жилые дома ночью. Она только что сфотографировала огромное прямоугольное здание, которое можно представить как таблицу из $$$n \times m$$$ окон. Это означает, что в здании $$$n$$$ этажей и на каждом этаже ровно $$$m$$$ окон. Каждое окно либо тёмное, либо светлое, то есть в комнате за ним горит свет.
Энни знает, что каждая квартира в этом доме либо однокомнатная, либо двухкомнатная. Каждая однокомнатная квартира представлена на фотографии ровно одним окном, а каждая двухкомнатная квартира представлена на фотографии двумя подряд идущими окнами на одном этаже. Более того, $$$m$$$ гарантированно делится на $$$4$$$ и известно, что на каждом этаже ровно $$$\frac{m}{4}$$$ двухкомнатных квартир и ровно $$$\frac{m}{2}$$$ однокомнатных квартир. Точное расположение квартир неизвестно и может быть разным для каждого этажа.
Энни считает, что квартира заселена, если хотя бы в одном из её окон горит свет. Теперь она задаётся вопросом, какое может быть минимальное и максимальное количество заселённых квартир в доме, если судить по данной фотографии?
Формально, для каждого из этажей Энни придумывает возможное расположение квартир, в котором есть ровно $$$\frac{m}{4}$$$ двухкомнатных квартир (два последовательных окна) и $$$\frac{m}{2}$$$ однокомнатных квартир (одно окно). Затем она подсчитывает общее количество квартир, в которых есть хотя бы одно светлое окно. Какое минимальное и максимальное число она может получить?
Первая строка входных данных содержит два положительных целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n \cdot m \leq 5 \cdot 10^5$$$) — количество этажей в здании и количество окон на этаже соответственно. Гарантируется, что $$$m$$$ делится на $$$4$$$.
Затем следует $$$n$$$ строк, каждая из которых содержит $$$m$$$ символов. $$$j$$$-й символ $$$i$$$-й строки равен «0», если $$$j$$$-е окно на $$$i$$$-м этаже тёмное, и равен «1», если это окно светлое.
Выведите два целых числа, минимальное и максимальное возможное количество заселённых квартир, если на каждом этаже возможно своё собственное расположение $$$\frac{m}{4}$$$ двухкомнатных и $$$\frac{m}{2}$$$ однокомнатных квартир.
5 4 0100 1100 0110 1010 1011
7 10
1 8 01011100
3 4
В первом примере каждый этаж состоит из одной двухкомнатной квартиры и двух однокомнатных квартир.
При следующей планировке квартир достигается минимально возможное количество заселённых квартир, равное $$$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|
Название |
---|