Codeforces Round 282 (Div. 1) |
---|
Закончено |
Малек — богатый человек. К тому же он очень щедрый. Поэтому он решил разделить свои деньги между бедняками. Благотворительному фонду известно n бедняков, занумерованных числами от 1 до n. Фонд дал Малеку q рекомендаций. Рекомендация — это отрезок [l, r], обозначающий, что фонд рекомендовал Малеку дать по доллару каждому человеку, чей номер есть в этом отрезке.
У фонда необычные правила касательно рекомендаций. Согласно этим правилам, рекомендации даются так, что для любых двух рекомендаций [a, b] и [c, d] выполняется одно из следующих условий:
Эффект благотворительности — это максимальное значение суммы денег, имеющейся у бедняка после того, как Малек закончит раздавать свои деньги. Для каждой рекомендации фонд знает вероятность того, что Малек её примет. Фонд хочет знать математическое ожидание эффекта благотворительного акта Малека. Они попросили Вас помочь им в нахождении этой величины.
Вам дан список рекомендаций, для каждой рекомендации также дана вероятность того, что Малек примет её. Вам дано количество денег, изначально имеющееся у каждого человека. Требуется найти математическое ожидание эффекта благотворительности.
В первой строке даны два целых числа через пробел — n, q (1 ≤ n ≤ 105, 1 ≤ q ≤ 5000).
Во второй строке содержатся n разделённых пробелами целых чисел a1, a2, ..., an (0 ≤ ai ≤ 109), обозначающие, что у человека i изначально есть ai долларов.
В каждой из следующих q строк записано по три целых числа через пробел li, ri, pi (1 ≤ li ≤ ri ≤ n, 0 ≤ p ≤ 1), где li и ri — два числа, описывающих отрезок рекомендации, а pi — вещественное число, данное ровно с тремя знаками после десятичной точки, равное вероятности того, что Малек примет данную рекомендацию.
Обратите внимание, что один и тот же отрезок может появляться в рекомендациях несколько раз.
Выведите математическое ожидание. Ответ будет засчитан, если его абсолютная или относительная погрешность будет составлять не более 10 - 6.
5 2
1 7 2 4 3
1 3 0.500
2 2 0.500
8.000000000
5 2
281 280 279 278 282
1 4 1.000
1 4 0.000
282.000000000
3 5
1 2 3
1 3 0.500
2 2 0.250
1 2 0.800
1 1 0.120
2 2 0.900
4.465000000
Название |
---|