Dp[i][j] — мы стоим на перегоне i, j раз включали машину, последний разна этом перегоне. Скольким людям мы можем промыть мозги? Переход — перебираем, где включали в прошлый раз. Тогда мозги промыли всем, кто сел после k и выйдет после i.Это за O(n^5).

Теперь две оптимизации:

1) Когда перебираем k идём от i по убыванию и по ходу прибавляем тех, кто сел на последней станции

2) Для каждой станции прибавляемая величина — это сумма на некотором суффиксе, а эти суммы можно пред подсчитать

Каждая оптимизация съедает одну линию и мы получили решение за O(n^3)

переписал код, теперь он работает 0,3 секунды, но получает wa 8