Динамика dp[i][j] — минимальная суммарная сложность разбиения первых i рядов на j зон.
Пересчет: , где sum(a, b) — суммарная сложность пассажиров, сидящих на местах от a до b.
Как вычислить sum(a, b):
Считаем за O(NS) массив cnt[i][j] — количество человек стоящих перед i-ым в очереди, и садящихся на ряд j. Затем считаем массив префикс-сумм .
Тогда sum(a, b) = ps[b] - ps[a - 1].