感觉就是两个题硬揉在一起的缝合题，不太好评价。
解法
将问题拆成两个完全独立的部分。
对于离散食物，不难想到把每每个物品拆成若干物品做 01 背包，最坏复杂度为 $\mathcal{O}(nw^2)$（取决于每个物品的重量）。
考虑如何优化这个背包。不难发现所有重量为 $i$ 的物品中只有 $\dfrac{w}{i}$ 个可以对答案产生贡献，所以我们只取这些物品做背包即可，时间复杂度 $\mathcal{O}(nw \log w)$，其中 $\log$ 来自调和级数。
对于连续食物，我们可以贪心，将所有食物按照初始收益排序，称当前食物为目前初始收益最好的食物。不难发现吃当前食物一定不会使答案更劣。如果吃了一定数量的当前食物使当前食物和下一个食物的初始收益相同时，我们可以合并两个食物，设当前食物衰变常量（机翻的）、下一个食物衰变常量、合并后食物的衰变常量分别为 $t_1,t_2,t$，则可列出 $t_0 \times w - \dfrac{1}{2} \times \dfrac{t_1}{t_1 + t_2} \times w^2 + t_0 \times w - \dfrac{1}{2} \times \dfrac{t_2}{t_1 + t_2} \times w^2 = t_0 \times w - \dfrac{1}{2} t \times w^2$，所以 $t = \dfrac{t_1 \times t_2}{t_1 + t_2}$。
最后将两个部分合并就行了。
代码
#include<bits/stdc++.h>
namespace fast_IO
{
/**
* useless things
*/
};
using namespace fast_IO;
#define int long long
#define double long double
const int N=300,W=10010;
int n,w;
double ans=LONG_LONG_MIN;
struct Discrete // 离散
{
int f[W];
std::vector< std::pair<int,int> > v[W];
std::vector<int> tmp;
inline void add(const int w0,const int t0,const int delt)
{
v[w0].push_back(std::make_pair(t0,delt));
}
inline void solve()
{
memset(f,128,sizeof(f)),f[0]=0;
for(int i=1;i<=w;i++)
if(!v[i].empty())
{
tmp.clear();
for(int j=0;j<v[i].size();j++)
for(int k=1;k<=w/i;k++) tmp.push_back(v[i][j].first-(k-1)*v[i][j].second);
std::nth_element(tmp.begin(),tmp.begin()+w/i,tmp.end(),std::greater<int>());
for(int j=0;j<w/i;j++)
for(int k=w;k>=i;k--) if(f[k-i]!=-9187201950435737472) f[k]=std::max(f[k],f[k-i]+tmp[j]);
}
}
};
struct Continuous // 连续
{
double f[W],last;
std::vector< std::pair<int,int> > v;
std::vector< std::pair<double,double> > tmp;
inline void add(const int t0,const int delt)
{
v.push_back(std::make_pair(t0,delt)),tmp.push_back(std::make_pair(0,0));
}
inline void solve()
{
memset(f,0,sizeof(f));
std::sort(v.begin(),v.end(),std::greater< std::pair<int,int> >());
for(int i=1;i<=w;i++)
{
last=i;
for(int j=0;j<v.size();j++) tmp[j]=v[j];
for(int j=0;j<v.size();j++)
if(j+1<v.size())
{
if(last>(tmp[j].first-tmp[j+1].first)/tmp[j].second)
f[i]+=((tmp[j].first-tmp[j+1].first)/tmp[j].second)*
(tmp[j].first-0.5*tmp[j].second*((tmp[j].first-tmp[j+1].first)/tmp[j].second)),
last-=(tmp[j].first-tmp[j+1].first)/tmp[j].second,
tmp[j+1].second=tmp[j].second*tmp[j+1].second/(tmp[j].second+tmp[j+1].second);
else
{
f[i]+=last*(tmp[j].first-0.5*tmp[j].second*last);
break;
}
}else f[i]+=last*(tmp[j].first-0.5*tmp[j].second*last);
}
}
};
Discrete dis;
Continuous con;
char ch;
signed main()
{
in>>n>>w;
for(int i=1,w0,t0,delt;i<=n;i++)
{
in>>ch;
if(ch=='C') in>>t0>>delt,con.add(t0,delt);
else in>>w0>>t0>>delt,dis.add(w0,t0,delt);
}
con.solve(),dis.solve();
if(con.v.empty())
{
if(dis.f[w]==-9187201950435737472) std::cout<<"impossible";
else std::cout<<std::fixed<<std::setprecision(7)<<dis.f[w];
return 0;
}
for(int i=0;i<=w;i++) if(dis.f[i]!=-9187201950435737472) ans=std::max(ans,dis.f[i]+con.f[w-i]);
std::cout<<std::fixed<<std::setprecision(7)<<ans;
return 0;
}
