Нехай — позиція -го міста. Нехай міста в маршруті — i_1, i_2, \ldots, i_k. Тоді сумарна довжина маршруту — \sum_{1 \le i \le k-1}|P_{i+1}-P_i|.
Отже, вклад міста визначається лише тим, по яку сторону воно знаходиться від своїх сусідів. Будемо додавати міста в порядку зростання, і тримати в кількість міст, які ми вибрали на цю мить, скільки шматків маршруту в нас є на цю мить, сумарний вклад міст до цього моменту по модулю , а також чи додали ми вже початок та кінець всього маршруту. При обробці чергового міста перебирайте всі варіанти: місто до нього в маршруті знаходиться до нього/після нього/воно само є лівим кінцем маршруту, і так само для правого сусіда в маршруті.
Обмеження в задачі достатньо малі, щоб таке рішення за O(nk^2 m) з великою константою проходило в TL.