比赛 |
清华集训2017模板练习 |
评测结果 |
AAAAAAAAAA |
题目名称 |
货币兑换 |
最终得分 |
100 |
用户昵称 |
栋霸霸 |
运行时间 |
0.685 s |
代码语言 |
C++ |
内存使用 |
10.24 MiB |
提交时间 |
2017-07-17 14:15:34 |
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N=100010;
double a[N],b[N],ra[N],v[N];
struct Data
{
int t;
double k,b,x;
} g[N],p[N],q[N];
inline bool cmp(const Data &x,const Data &y)
{
return x.x<y.x;
}
inline void solve(int l,int r)
{
if(l==r) return;
int mid=(l+r)>>1,p1=l,p2=mid+1,st=1,ed=0;
double Mx=0;
for(int i=l; i<=r; i++)
{
if(g[i].t<=mid) p[p1++]=g[i];
else p[p2++]=g[i];
}
for(int i=l; i<=r; i++) g[i]=p[i];
solve(l,mid);
for(int i=l; i<=mid; i++)
{
while(st<ed&&(g[i].k-q[ed].k)*(q[ed-1].b-g[i].b)>=(g[i].k-q[ed-1].k)*(q[ed].b-g[i].b)) ed--;
q[++ed]=g[i],Mx=max(Mx,v[g[i].t]);
}
sort(g+mid+1,g+r+1,cmp);
for(int i=mid+1; i<=r; i++)
{
while(st<ed&&q[st].k*g[i].x+q[st].b<=q[st+1].k*g[i].x+q[st+1].b) st++;
v[g[i].t]=max(v[g[i].t],max(Mx,a[g[i].t]*(q[st].k*g[i].x+q[st].b)));
g[i].k=v[g[i].t]/(a[g[i].t]*ra[g[i].t]+b[g[i].t]),g[i].b=g[i].k*ra[g[i].t];
}
solve(mid+1,r);
p1=l,p2=mid+1;
for(int i=l; i<=r; i++)
{
if(p2>r||(p1<=mid&&g[p1].k<=g[p2].k)) p[i]=g[p1++];
else p[i]=g[p2++];
}
for(int i=l; i<=r; i++) g[i]=p[i];
}
int main()
{
freopen("cash.in","r",stdin);
freopen("cash.out","w",stdout);
int n;
cin>>n>>v[0];
for(int i=1; i<=n; i++)
{
scanf("%lf%lf%lf",&a[i],&b[i],&ra[i]);
v[i]=v[0],g[i].t=i;
g[i].x=b[i]/a[i],g[i].k=v[i]/(a[i]*ra[i]+b[i]),g[i].b=g[i].k*ra[i];
}
solve(1,n);
printf("%.3f\n",v[n]);
return 0;
}