#P3795. 魏总刷DP

    ID: 2997 传统题 1000ms 256MiB 尝试: 12 已通过: 11 难度: 7 上传者: 标签>CF2200提高几何概率直线上包络单调栈分段线性函数精确积分

魏总刷DP

题目描述

魏总从上课开始先睡 kk 秒,醒来后同时做 nn 道题。第 ii 题原需 uiu_i 秒,醒来后用时变为 kuiku_i 秒,因此它在上课开始后的第 k(1+ui)k(1+u_i) 秒完成。

睡眠时间 kk 在 (0,m](0,m] 上均匀分布,课时 TT 在 [L,R][L,R] 上均匀分布,两者相互独立。本站按此分布计算概率。

对于 HARD 题,魏总要求最晚在下课后的 lateilate_i 秒内完成。对于 EASY 题,他要求最晚在下课前的 restirest_i 秒完成。求所有题都满足各自时限的概率。

输入格式

第一行一个整数 nn。第二行三个实数 m,L,Rm,L,R。第三行 nn 个正整数 uiu_i。

接下来 nn 行依次描述各题。每行给出 HARD 和整数 lateilate_i,或 EASY 和整数 restirest_i。

输出格式

输出一行概率,保留四位小数。

样例

2
1.50 0.630 1.810
2 2
EASY 1
EASY 0
0.0618

数据范围

1≤n≤1051\le n\le10^5,0<m<1050<m<10^5,0<L<R<1050<L<R<10^5,0≤latei,resti≤1050\le late_i,rest_i\le10^5。