Петя на велосипеде
Первоисточник: Казань
URL первоисточника: http://www.icl.ru/images/tournament/Problems/train/train9.htm
Задачу добавил: alef
Успешно сдано решений: 1
Петя любит ездить на своем велосипеде, но поскольку город, в котором он живет, довольно большой, он иногда использует систему городского общественного транспорта для передвижения. У него есть складной велосипед, который он может взять в автобус. Но когда автобус подъезжает к приятной части города, он сходит и едет на велосипеде. Петя едет вдоль автобусного маршрута, пока он не доезжает до дома, или пока не попадает в часть города, которую он не любит. В пос¬леднем случае, он садится на автобус и едет до дома. За годы опыта, Петя оценил каждую дорогу по целочисленной шкале симпатичности. Неотрицательная симпатичность отвечает дороге, кото¬рую Петя любит, а отрицательная - которую нет. Петя планирует так сойти с автобуса и затем сесть на него снова (либо не делать некоторых из этих действий) чтобы сумма симпатичностей дорог, по которым он проедет, была максимальна. Это означает, что иногда он может проехать по дорогам, которые он не любит, если они соединяют участки пути, которые содержат дороги, сим¬патичность которых достаточна, чтобы компенсировать это. Случается и такое, что никакая часть пути не подходит для езды на велосипеде, так что Петя едет на автобусе всю дорогу. Наоборот, может случиться, что путь такой симпатичный, что Пете вообще не потребуется автобус. Посколь¬ку в городе много автобусных маршрутов, каждый с несколькими остановками, то Пете нужна компьютерная программа, чтобы найти лучшую часть пути для каждого маршрута.
Входной файл INPUT.TXT
содержит информацию об одном автобусном маршруте. В первой строке содержится число N (2 <= N <= 20000) - количество остановок в маршруте. Следующие N-1 строк содержат симпатичности ai (-32768 <= ai <= 32767) пути между соответствующими остановками (между 1-й и 2-й, между 2-й и 3-й... между N-1-й и N-й.)
Выходной файл OUTPUT.TXT
должен содержать три целых числа: начальную и конечную остановки - i и j (которые показывают часть пути, на котором достигается наибольшая сумма S симпатичностей) и число S - сумма симпатичностей между ними. Если более одного участка дают максимальную симпатичность, выведите более длинный (с большим j-i). Чтобы разрешить неоднозначности при равенстве длин, выберите участок с меньшим i. Если же максимальная сумма отрицательна, выведите "NO".
Примеры
| INPUT.TXT | OUTPUT.TXT |
10 4 -5 4 -3 4 4 -4 4 -5 | 3 9 9 |
4 -2 -3 -4 |
NO |