Book rental#215

Book rental (Editorial)

Книжку можна почати читати лише в момент t_i, і тоді вона зайнята до моменту t_i + l_i. Отже, кожна книжка — це відрізок часу [t_i,\; t_i + l_i) з вагою a_i, а нам треба вибрати попарно неперетинні відрізки з максимальною сумарною вагою. Це класична задача про зважений розклад.

Оскільки моменти часу невеликі (t_i, l_i \le 10^6, тому кінець не перевищує 2 \cdot 10^6), зручно вести динаміку за часом, а не за номером книжки.

Нехай — максимальна сумарна цікавість, яку можна набрати, якщо до моменту ми вже вільні. Тоді, ідучи по від до максимуму:

  • \mathrm{dp}[T] \ge \mathrm{dp}[T-1] — можна нічого не робити;

  • для кожної книжки з t_i + l_i = T маємо \mathrm{dp}[T] \ge \mathrm{dp}[t_i] + a_i — почали читати її рівно в момент t_i.

Щоб швидко знаходити книжки із заданим кінцем, згрупуємо їх за значенням t_i + l_i (наприклад, списками або сортуванням підрахунком).

Відповідь — у найбільшому моменті часу.

Складність — \mathcal{O}(n + T_{\max}). Цікавості сягають 10^9, а книжок до 10^6, тому суму накопичуйте у 64-бітному типі.