Рапорт

Решение на 51 балл: Обе части рапорта можно написать, если ширина левой части рулона не меньше максимальной длины слова в первой части рапорта, и, аналогично, ширина правой части рулона не меньше максимальной длины слова во второй части рапорта. Переберем положение вертикальной черты, при котором рапорт возможно написать. После этого, проэмулируем процесс написания слов и вычислим длину рулона для данной позиции вертикальной черты. Ответом является минимальная длина рулона по всем положениям черты.

Решение на 100 баллов: Заметим, что при сдвигании вертикальной черты вправо (то есть, при увеличении ширины левой части рулона и уменьшении ширины правой части рулона), длина первой части рапорта будет уменьшаться, а длина второй части рапорта будет увеличиваться (длиной части рапорта назовем минимальную длину рулона, необходимую, чтобы написать эту часть рапорта на соответствующей части рулона).

Поэтому, используя двоичный поиск можно найти две соседних вертикальных черты, что если провести одну из них, левая часть будет длиннее правой, а если вторую, то наоборот. Заметим, что среди ответов для этих двух черт обязательно есть оптимальный ответ.

Для того, чтобы найти длины частей для определенной черты, нужно просто проэмулировать процесс, добавляя по одному слову.

Итоговая асимптотика: $$$O((n + m) \log w)$$$.