比赛 清华集训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;
}