Лучшие помощники
14 марта 2023 14:57
139

/*14.1. Бонни и Клайд (6) Задача выполнена студентом ПС 21 Желаевым Денисом.

Бонни и Клайд задумали ограбить в некотором городе два банка. Все N банков в этом городе находятся на его главной улице.

Для каждого i-го банка известны расстояние от начала улицы Xi и имеющаяся сумма денег Wi. Чтобы было меньше шума,

Бонни и Клайд собираются выбрать такую пару банков, чтобы расстояние между ними было не менее d.

Вместе с тем они хотят, чтобы сумма денег в обоих банках оказалась максимальной. Как это сделать?

Ввод из файла INPUT.TXT. В первой строке указаны через пробел целые значения N и d - число банков и минимально допустимое расстояние между парой банков,

которые можно грабить (2 ≤ N ≤ 2·105, 1 ≤ d ≤ 10^8).

В каждой из следующих N строк содержится через пробел два целых числа Xi и Wi - расстояние от начала улицы до банка и имеющаяся в банке наличность (1 ≤ Xi, Wi ≤ 108).

Строки следуют в порядке увеличения расстояний Xi.

Вывод в файл OUTPUT.TXT. В первой строке вывести сумму денег в выбранных банках.

Во второй строке вывести через пробел в любом порядке номера двух требуемых банков.

Если имеется несколько решений, вывести любое из них. Если решений нет, вывести строку -1 -1.

Пример

Ввод

6 3

1 1

3 5

4 8

6 4

10 3

11 2

Вывод

11

5 3

*/


1 ответ
Посмотреть ответы
This is a problem statement for a programming task called "Bonnie and Clyde". The task involves two robbers who want to rob two banks in a city with N banks. Each bank has a distance from the start of the street and an amount of money. The robbers want to choose two banks that are at least d distance apart and have the maximum amount of money combined. The input is provided in a file called INPUT.TXT, which contains the values of N and d, followed by N lines with the distance and money values for each bank. The output should be written to a file called OUTPUT.TXT, with the maximum amount of money and the numbers of the two chosen banks. If there are multiple solutions, any one of them can be output. If there are no solutions, the output should be "-1 -1".
0
·
Хороший ответ
14 марта 2023 14:58
Остались вопросы?
Найти нужный