Задача на нахождение максимальной суммы

Подскажите алгоритм решения задачи.

Проходит очередной финал Start[c]up, поэтому необходимо заказать пиццу для финалистов, участвующих в соревновании в офисе компании. Существует всего два типа пиццы (конечно нет, но в этой задаче будем считать, что да), все пиццы содержат одинаковое число S кусочков.

Известно, что i-й участниц съест si кусочков пиццы, и получит ai единиц счастья от съедания каждого кусочка пиццы первого типа, и bi единиц счастья от съедания каждого кусочка пиццы второго типа. Мы можем заказать любое число пицц первого и второго типов, но мы хотим заказать минимальное число пицц, необходимое для того, чтобы все участники могли съесть необходимое каждому число кусочков. Учитывая это ограничение, какое максимальное суммарное число единиц счастья могут получить участники?

Входные данные
Первая строка содержит целые числа N и S (1 ≤ N ≤ 105, 1 ≤ S ≤ 105) — число участников и число кусочков пиццы в каждой пицце, соответственно.

Далее следуют N строк. i-я из них содержит целые числа si, ai и bi (1 ≤ si ≤ 105, 1 ≤ ai ≤ 105, 1 ≤ bi ≤ 10 5) — количество кусочков пиццы, которые съест i-й участник, счастье, которое он получает от каждого съеденного кусочка первого типа, и счастье, которое он получает от каждого съеденного кусочка второго типа, соответственно.

Выходные данные
Выведите максимальное суммарное счастье, которое могут получить участники.

Примеры
входные данные
3 12
3 5 7
4 6 7
5 9 5
выходные данные
84
входные данные
6 10
7 4 7
5 8 8
12 5 8
6 11 6
3 3 7
5 9 6
выходные данные
314

0

Жуть! И какие же монстры придумывают эти сказочки!?
Но на диагональный взгляд - простейшая задача линейного программирования.
Если я ошибся, прошу меня извинить. Ибо читать эту бредятину иначе, чем по диагонали - тошно. Да и по диагонали - тоже тошно.

0

Байт, я поняла, что тут нужно. Надо в каждой этой строке (7 4 7, 5 8 8) найти два наибольших, их переможить и сложить с другими произведениями наибольших в остальных строках. Можете помочь с кодом? Я долблюсь уже долго и что-то не получается.

0

Сообщение от MariaFitzgerald Я долблюсь уже долго

Уважаемая Дятлиха! Если вы покажете результаты вашего долбления в виде кода, возможно, кто-то и попытается вам помочь

0

Если вообразить себя поручиком Ржевским и прочитать третье сообщение автора, то способ решения проблемы приобретает пикантный смысл

0

Здравствуйте. нет, не просто перемножить, задача несколько сложнее. давайте разберем первый пример;:
цитата
3 12
3 5 7
4 6 7
5 9 5
выходные данные
84
"
решение: на первом этапе считаем, сколько кусочков съедят спортсмены. (3 ++ 4 + 5) = 12.
2) определяем минимально возможное количество пиц, которые необходимо заказать: делим количество кусочков на количество кусочков в одной пице с округлением вверх 12/12 = 1. следовательно, необходимо заказать одну пицу.
далее методом перебора смотрим: пусть заказана пицца 1: считаем, что получилось, складывая суммы 3*5 + 4*6 + 9*5 = 15 + 24 + 45 = 84.
проверяем, если заказана вторая пицца : 3*7 + 4*7 + 5*5 = 21 + 28 + 25 = = 64. т.е. счастья меньше, следовательно, была заказана пицца 1.
если пицц больше одной, то необходимо перебрать все варианты, например, во второй задачи заказали 4 пиццы (получилось 38 кусочков, кто доест еще 2 в задаче не сказано).
В какой дисциплине вам дали эту задачу? зная, что вы проходите, проще будет предлагать решение.

0