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