#P4073. [Wf2014]Buffed Buffet

    ID: 2778 传统题 2000ms 128MiB 尝试: 92 已通过: 18 难度: 9 上传者: 标签>CF2600省选/NOI-线性 DP凸包优化 DP事件排序分段线性函数精确积分

[Wf2014]Buffed Buffet

题目描述

自助餐厅里有 nn 种食物,分为两大类,为 “离散食物”和“连续食物”。你可以通过吃食物来获得收益。

离散食物用 (w,t0,Δt)(w,t_0,\Delta t) 描述。对于这种食物,你只能吃整数个,每个重为 ww。吃的第一个收益为 t0t_0,后面每吃一个收益减少 Δt\Delta t。具体的,吃的第 ii 个这种食物 (从 11 开始标号),收益为 t0−(i−1)Δtt_0-(i-1)\Delta t。

连续食物用 (t0,Δt)(t_0,\Delta t) 描述。对于这种食物,你可以吃任意食物的重量。如果你吃的重量为 ww,获得的收益是 t0w−12Δtw2t_0w-\dfrac{1}{2}\Delta t w^2。

你现在要吃重量和 恰好 为 WW 的食物。最大化你的收益。

输入格式

第一行是 n,Wn,W,接下来每行先来一个字母,如果是 C 表示连续食物,后面跟两个数表示 t0,Δtt_0,\Delta t;如果是 D 表示离散食物,后面跟三个数,表示 w,t0,Δtw,t_0,\Delta t。

输出格式

一行一个数表示答案。相对或绝对误差不超过 1e−61e-6。

2 15
D 4 10 1
C 6 1
40.500000000
3 15
D 4 10 1
C 6 1
C 9 3
49.000000000
2 19
D 4 5 1
D 6 3 2
impossible

数据规模与约定

对于 100%100\% 的数据满足,n≤250,W≤10000n\le 250,W\le 10000。

对于离散食物,满足 1≤w≤100001\le w\le 10000。

对于所有食物,满足 0≤t0,t≤100000\le t_0,t\le 10000。