Блог пользователя atyetti9

Помогите с задачей.
Автор atyetti9, 10 лет назад, По-русски

Вот ссылка на тесты.

UPD: У кого имеется разбор X Жауты скиньте пожалуйста.

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Был не прав.

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Не верится, что функция будет выпуклой.

    → Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Может быть, что где-то с права от точки 2/3 отрезка есть точка где энергии хватит на все.

    → Ответить
»
10 лет назад, # |
← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

Вычтем в каждой точке из генерируемой энергии расстояние до предыдущего

Теперь пусть фиксировано начало. Нам нужно найти самый длинный отрезок(так как кол-во голды везде положительное), который тут начинается и при этом сумма энергий на отрезке не менее -(кол-ве энергии генерируемое в начале)

Давайте построим ДО. Элемент — сумма энергий от начала. Операция — максимум. Теперь нужно спуском по дереву находить последнее место, где >= C. (при этом C будет сдвинуто на сумму на префиксе)

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Кстати, об этой задаче когда-то уже спрашивали.

→ Ответить