Изменения

}}

===Решение===

Сначала проверим, что <tex>2*B>A</tex>. Если это условие не выполнено, то все выгодней замостить только плитками <tex>1 \times 1</tex> и больше нечего считать. Теперь на нужно максимизировать количество плиток ценой А.

Раскрасим наш паркет по принципу шахматной доски, тогда один конец плитки <tex>2 \times 1</tex> будет лежать на черной клетке, другой — на белой. Итак, построим двудольный граф, одна доля которого будет содержать белые клетки, другая — черные. Ребра весом в <tex>1</tex> проведем между граничащими клетками. Добавим исток с ребрами в белые вершины весом в бесконечность и сток с ребрами из черных клеток весом тоже в бесконечность. Пускай <tex>f</tex> — величина найденного максимального потока между истоком и стоком, это и будет количество плиток <tex>2 \times 1</tex>. Ответом к задаче будет величина <tex>f*A+(K-f)*B</tex>, где <tex>K</tex> — общее количество испорченных клеток.

== Источники информации ==

* [https://icpc.baylor.edu/regionals/finder/west-siberian-subregional-2016 The 2016 West Siberian Subregional Contest]