Задача бэкенд Тинькофф (Hard).

Представьте, что у вас есть матрица из 0 и 1 размера n * m, где n * m <= 1e6. В матрице на каждом столбце есть ровно один непрерывный отрезок из единичек.
Например:
0 1 1
0 0 1
1 0 0

За одну операцию вы можете выбрать отрезок из единиц (по столбцу) и переместить их наверх/вниз на один, если не выйдете за пределы массива.
Например я из примера выше могу получить за одну операцию
0 1 0
0 0 1
1 0 1

Расстановка является хорошей, если можно из каждой единицы добраться до каждой другой единицы двигаясь в соседние клетки по 4 сторонам.

Ваша задача за минимальное количество действий получить хорошую расстановку.

Решение:
Пусть, dp[i][j] - минимальное количество операций необходимое, чтобы получить хорошую расстановку для столбцов 1, 2, 3, ..., i, но так, чтобы отрезок из единиц на i-том столбце покрывал позицию (i, j).

Давайте научимся обновлять дпшку. Пусть на i том столбце единички изначально находятся в позициях [s, e] (У нас же единички - это непрерывный отрезок по каждому столбцу).
Как обновляется dp[i][j], если s <= j <= e ?
Конечно же через min(dp[i - 1][s], dp[i - 1][s + 1], ..., dp[i - 1][e])
Отлично, а как быть с остальными j, которые лежат вне отрезка [s, e] ?

Давайте начнем наш отрезок двигать вверх, то есть наш отрезок [s, e] переместиться в [s - 1, e - 1], потом в [s-2, e-2] и так далее. По факту мы ходим скользящим окном и нам надо быстро узнавать минимум на отрезке для dp[i - 1], например, когда отрезок переместился на [s-1, e-1] мы обновляем нашу дпшку через 1 + min(dp[i-1][s-1], dp[i-1][s], ..., dp[i-1][e-1]).

Задача сводится к тому, чтобы быстро находить минимум на в скользящем окне.
ДО - не рекомендуется писать, так как будет TL.

Монотонный стек или Sparce Table самое то!
Если хочешь научиться решать такие задачи то приходи на курсы Алгоритмы Хард, которые начнутся 28 июля.

Асимптотика алгоритма O(n*m)
Код в комментариях