比赛 清华集训2017模板练习 评测结果 AAAAAAAAAA
题目名称 货币兑换 最终得分 100
用户昵称 FoolMike 运行时间 0.680 s
代码语言 C++ 内存使用 42.28 MiB
提交时间 2017-07-17 17:48:01
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
typedef long double db;
const db eps=1e-9;
const int N=1e5+10;
int n;
db a[N],b[N],rate[N],ans[N];
struct ask{int id;db k;}Q[20][N];
void mergesort(int l,int r,int h){
	if (l==r) return;
	ask *a=Q[h],*b=Q[h+1];
	for (int i=l;i<=r;i++) b[i]=a[i];
	int mid=(l+r)>>1;
	mergesort(l,mid,h+1);
	mergesort(mid+1,r,h+1);
	int i=l,j=mid+1,p=l;
	while (i<=mid&&j<=r) a[p++]=(b[i].k<b[j].k?b[i++]:b[j++]);
	for (;i<=mid;a[p++]=b[i++]);
	for (;j<=r;a[p++]=b[j++]);
}
typedef pair<db,db> pr;
pr p[N],P[N],q[N];
db k(pr x,pr y){
	if (y.first-x.first<eps) return y.second>x.second?1e9:-1e9;
	return (x.second-y.second)/(x.first-y.first);
}
void solve(int l,int r,int h){
	if (l==r){
		ans[l]=max(ans[l],ans[l-1]);
		db k=ans[l]/(a[l]*rate[l]+b[l]);
		p[l]=pr(k*rate[l],k);
		return;
	}
	int mid=(l+r)>>1;
	solve(l,mid,h+1);
	int head=1,tail=0;
	for (int i=l;i<=mid;i++){
		for (;tail>1&&k(q[tail-1],q[tail])<k(q[tail],p[i]);tail--);
		q[++tail]=p[i];
	}
	ask *que=Q[h];
	for (int i=mid+1;i<=r;i++){
		for (;head<tail&&-k(q[head],q[head+1])<que[i].k;head++);
		int id=que[i].id;
		ans[id]=max(ans[id],a[id]*q[head].first+b[id]*q[head].second);
	}
	solve(mid+1,r,h+1);
	int i=l,j=mid+1,pos=l;
	while (i<=mid&&j<=r) P[pos++]=(p[i]<p[j]?p[i++]:p[j++]);
	for (;i<=mid;P[pos++]=p[i++]);
	for (;j<=r;P[pos++]=p[j++]);
	for (i=l;i<=r;i++) p[i]=P[i];
}
int main()
{
	freopen("cash.in","r",stdin);
	freopen("cash.out","w",stdout);
	scanf("%d%Lf",&n,&ans[0]);
	for (int i=1;i<=n;i++){
		scanf("%Lf%Lf%Lf",&a[i],&b[i],&rate[i]);
		if (a[i]<eps) a[i]=eps;
		if (b[i]<eps) b[i]=eps;
		Q[0][i]=(ask){i,a[i]/b[i]};
	}
	mergesort(1,n,0);
	solve(1,n,1);
	printf("%.3Lf\n",ans[n]);
	return 0;
}