| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 53 | 3 | 2 | 12.500% |
Компания тестирует технологию получения антивещества, используемого в качестве топлива в межпланетном звездолёте. Антивещество получается в результате специальных экспериментов в реакторе.
Известно $n$ типов экспериментов, приводящих к получению антивещества. В результате проведения эксперимента $i$-го типа в выходной контейнер реактора добавляется от $l_i$ до $r_i$ граммов антивещества. Из соображений безопасности запрещается накапливать в контейнере более $a$ граммов антивещества.
Затраты на проведение эксперимента $i$-го типа составляют $c_i,ドル а стоимость одного грамма полученного антивещества составляет 10ドル^9$.
Если после проведения экспериментов в контейнере образовалось $t$ граммов антивещества, а суммарные затраты на проведение экспериментов в реакторе составили $s,ドル то прибыль определяется по формуле ($t \cdot 10^9 - s$). Компании необходимо разработать стратегию проведения экспериментов, позволяющую максимизировать прибыль, которую можно гарантированно получить.
В зависимости от результатов предыдущих экспериментов стратегия определяет, эксперимент какого типа следует провести, или решает прекратить дальнейшее выполнение экспериментов. Стратегия позволяет гарантированно получить прибыль $x,ドル если при любых результатах проведения экспериментов: во-первых, в контейнере реактора оказывается не более $a$ граммов антивещества, во-вторых, прибыль составит не менее $x$.
Например, пусть возможен только один тип эксперимента, порождающий от 4 до 6 граммов антивещества, затраты на его проведение равны 10, а вместимость контейнера составляет 17 граммов. Тогда после двукратного проведения эксперимента в контейнере может оказаться от 8 до 12 граммов антивещества. Если получилось 12 граммов, то больше проводить эксперимент нельзя, так как в случае получения 6 граммов антивещества контейнер может переполниться. В остальных случаях можно провести эксперимент в третий раз и получить от 12 до 17 граммов антивещества. В худшем случае придётся провести эксперимент трижды, затратив в сумме 30, прибыль составит $(12\cdot 10^9-30)=11,999円,999円,970円$.
Требуется написать программу, которая определяет максимальную прибыль $x,ドル которую гарантированно можно получить.
Первая строка входных данных содержит два целых числа: $n$ --- количество типов экспериментов и $a$ --- максимально допустимое количество антивещества в контейнере (1ドル \leq n \le 100,ドル 1ドル \leq a \leq 2\cdot 10^6$).
Следующие $n$ строк содержат по три целых числа $l_i,ドル $r_i$ и $c_i$ --- минимальное и максимальное количество антивещества, получаемое в результате эксперимента типа $i,ドル и затраты на эксперимент этого типа, соответственно (1ドル \leq l_i \leq r_i \leq a,ドル 1ドル \leq c_i \leq 100$).
Выходные данные должны содержать одно целое число --- максимальную прибыль $x,ドル которую гарантированно можно получить.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | $n = 1,ドル $a \le 1,000円$ |
| 2 | 10 | $n \leq 10,ドル $a \le 1,000円,ドル $l_i = r_i$ |
| 3 | 20 | $n \leq 10,ドル $a \le 1,000円$ |
| 4 | 20 | $n \leq 100,ドル $a \le 50,000円$ |
| 5 | 4 | $n \leq 100,ドル $a \le 100,000円$ |
| 6 | 4 | $n \leq 100,ドル $a \le 200,000円$ |
| 7 | 4 | $n \leq 100,ドル $a \le 300,000円$ |
| 8 | 4 | $n \leq 100,ドル $a \le 400,000円$ |
| 9 | 4 | $n \leq 100,ドル $a \le 500,000円$ |
| 10 | 4 | $n \leq 100,ドル $a \le 800,000円$ |
| 11 | 4 | $n \leq 100,ドル $a \le 1,100円,000円$ |
| 12 | 4 | $n \leq 100,ドル $a \le 1,400円,000円$ |
| 13 | 4 | $n \leq 100,ドル $a \le 1,700円,000円$ |
| 14 | 4 | $n \leq 100,ドル $a \le 2,000円,000円$ |
1 17 4 6 10
11999999970
2 11 2 2 100 3 5 5
9999999890