Спершу спростимо цільову функцію. Нехай обрано кемпінги з координатами x_1 < x_2 < \ldots < x_K. Коефіцієнт Z_i — це сума відстаней від -го відео-кафе до всіх інших, тому
Розкриємо подвійну суму, порахувавши, скільки разів кожен x_i входить зі знаком плюс і скільки зі знаком мінус. Він додається для всіх i - 1 менших індексів і віднімається для всіх K - i більших, тому
Отже, максимізувати треба лінійну функцію \sum_i x_i (2i - K - 1) — вагові коефіцієнти залежать лише від порядкового номера кафе, а не від того, який саме кемпінг обрано. Це і робить задачу динамічною.
Тепер обмеження. Сусідні кафе мають відстояти на ; крім того, відстань від Ужкачева () до першого кафе і від останнього кафе до Ужковеля () теж має лежати в .
Динаміка: нехай \mathrm{dp}[i][j] — максимальне значення суми, якщо -те за рахунком кафе побудовано в кемпінгу . Тоді
а база — \mathrm{dp}[i][1] = x_i (1 - K) для тих , у яких A \le x_i \le B. Відповідь — подвоєний максимум \mathrm{dp}[i][K] по кемпінгах з A \le S - x_i \le B.
Ключова оптимізація — у тому, що кемпінги вже відсортовані за координатою, тому множина допустимих i' для кожного — це суцільний відрізок індексів, який лише зсувається вправо зі зростанням . Тому максимум по ньому підтримується двома вказівниками та чергою з мінімумом (двобічною чергою) за на крок; можна й деревом відрізків за \mathcal{O}(\log N).
Загальна складність — , що при N, K \le 1000 цілком проходить. Координати сягають 10^9, а коефіцієнти — , тому суму рахуйте у 64-бітному типі.