Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2204. Киноакадемия
Преобразование или подсчет характеристики (например, сумма) заданной или вычисляемой последовательности
Олимпиадные задачи на русском языке
| 08/01/2015 | Подготовка к региональному этапу (изучение новых правил) (C) |
Ограничения: время – 1s/2s, память – 256MiB Ввод: cinema.in или стандартный ввод Вывод: cinema.out или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
В финал конкурса Киноакадемии вышли `n`
лучших кинофильмов 2014 года. В конкурсе награждаются фильмы в двух номинациях: лучшая режиссура и лучший сценарий.
По правилам конкурса в каждой
номинации должен быть награжден ровно один фильм, причём в разных номинациях – разные фильмы.
В ходе многочисленных опросов зрителей и кинокритиков удалось собрать данные, показывающие, какой
уровень ликования вызовет победа каждого фильма в каждой из номинаций. Дотошные журналисты на этом
не остановились и дополнительно выяснили, каким будет уровень ликования, если тот или иной фильм не
выиграет ни в одной из номинаций.
Требуется написать программу, которая по результатам опросов определяет наибольший суммарный уровень ликования,
которого можно добиться выбором фильмов для награждения в указанных номинациях.
Формат входных данных
В первой строке входного файла задано целое число n – количество кинофильмов, участвующих в финале конкурса
Киноакадемии. В следующих `n` строках содержатся по три целых числа `a_i,\ b_i,\ c_i` – уровень
ликования, если `i`-й фильм не выиграет ни в одной из номинаций, уровень ликования,
если этот фильм выиграет в номинации на лучшую режиссуру, и уровень ликования, если
этот фильм выиграет в номинации на лучший сценарий.
Формат выходных данных
Первая строка выходного файла должна содержать одно число – наибольший возможный суммарный
уровень ликования. Вторая строка должна содержать два целых числа – номера фильмов-победителей в
номинациях лучшая режиссура и лучший сценарий соответственно. Фильмы нумеруются натуральными
числами от 1 до `n`. Если оптимальных способов выбора награждаемых фильмов несколько, можно вывести
любой из них.
Система оценки
Данная задача содержит три подзадачи. Для оценки каждой подзадачи используется своя группа тестов.
Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.
Для каждой подзадачи сообщаются баллы за эту подзадачу и результат проверки программы на каждом тесте.
Подзадача 1
`2\ ≤\ n\ ≤\ 100`
`1\ ≤\ a_i,\ b_i,\ c_i\ ≤\ 10^5`
Подзадача оценивается в 20 баллов.
Подзадача 2
`2\ ≤\ n\ ≤\ 2000`
`1\ ≤\ a_i,\ b_i,\ c_i\ ≤\ 10^5`
Подзадача оценивается в 25 баллов.
Подзадача 3
`2\ ≤\ n\ ≤\ 10^5`
`1\ ≤\ a_i,\ b_i,\ c_i\ ≤\ 10^9`
Подзадача оценивается в 55 баллов.
Пример ввода
3 3 6 9 1 5 7 1 3 9
Пример вывода
17 2 3
Пояснение к примеру
В приведенном примере наибольший суммарный уровень ликования равен `3\ +\ 5\ +\ 9\ =\ 17`.
