Параллельные процессы

Вам дана информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостанавливать процесс нельзя. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно. Все независимые друг от друга процессы могут выполняться параллельно. При этом каждый процесс должен выполняться как можно раньше.

Требуется определить:

Входные данные

Входной файл INPUT.TXT состоит N строк, в каждой из которых записана информация об одном процессе, которая задается последовательностью целых чисел, разделенных пробелом: ID процесса B, время T выполнения процесса в миллисекундах, далее следуют ID процессов A, которые должны быть выполнены до начала выполнения процесса B. Если процессы типа A отсутствуют, то третье число в строке равно 0. Гарантируется, что все ID процессов различны и выполнение всех процессов возможно.

Ограничения: 1 ≤ N ≤ 1000, 1 ≤ ID ≤ 10⁹, 1 ≤ T ≤ 10⁶.

Выходные данные

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

1. Минимальное время в миллисекундах, через которое завершится выполнение всей совокупности процессов.
2. Максимальное количество одновременно выполняющихся процессов.
3. Время в миллисекундах, в течении которого выполняется максимально возможное количество процессов.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]