Решение задачи Дровосеки с Codeforces

Маленькая девочка Сьюзи каждый день слушает сказки перед сном. Сегодняшняя сказка была про дровосеков, поэтому маленькая девочка сразу же начала представлять себе, как дровосеки рубят деревья, и в её мыслях родилась ситуация, описанная ниже.

Есть n деревьев, расположенных вдоль дороги в точках с координатами x1, x2, ... , xn. Каждое дерево имеет свою высоту hi. Дерево можно срубить и повалить влево или вправо. Тогда оно будет занимать отрезки [xi - hi, xi] и [xi;xi + hi] соответственно. Пока дерево не срублено, оно занимает точку с координатами xi. Дерево можно повалить, если на отрезке, который оно должно занимать после сваливания, нет ни одной занятой точки. Дровосеки хотят заготовить как можно большее число деревьев, поэтому Сьюзи стало интересно, какое наибольшее количество деревьев можно повалить.