萌新求助卡精度
查看原帖
萌新求助卡精度
610557
shinzanmonoszm 妹妹楼主2023/6/5 20:46

#include<iostream>
#include<algorithm>
#include<queue>
const int sz=1e5+10;
double A[sz],B[sz],r[sz],k[sz],b[sz],c[sz],cc[sz];
struct ST{
    int tree[sz<<2];
    double f(int x,int id){
        return k[id]*cc[x]+b[id];
    }
    void update(int p,int ln,int rn,int id){
        if(ln==rn){
            if(f(ln,tree[p])<f(ln,id))tree[p]=id;
            return;
        }
        int mid=ln+rn>>1;
        if(f(mid,tree[p])<f(mid,id))std::swap(id,tree[p]);
        if(f(ln,id)>f(ln,tree[p]))update(p<<1,ln,mid,id);
        if(f(rn,id)>f(rn,tree[p]))update(p<<1|1,mid+1,rn,id);
    }
    double query(int p,int ln,int rn,int id){
        if(ln==rn)return f(id,tree[p]);
        int mid=ln+rn>>1;
        if(id<=mid)return std::max(f(id,tree[p]),query(p<<1,ln,mid,id));
        else return std::max(f(id,tree[p]),query(p<<1|1,mid+1,rn,id));
    }
}st;
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n,m;
    std::cin>>n>>m;
    for(int i=1;i<=n;i++)
        std::cin>>A[i]>>B[i]>>r[i],cc[i]=c[i]=A[i]/B[i];
    std::sort(cc+1,cc+n+1);
    int head=1,tail=1;
    double f=m;
    for(int i=1;i<=n;i++){
        int id=std::lower_bound(cc+1,cc+n+1,c[i])-cc;
        f=std::max(f,st.query(1,1,n,id)*B[i]);
        b[i]=f/(A[i]*r[i]+B[i]),k[i]=b[i]*r[i];
        st.update(1,1,n,i);
    }
    std::cout<<f;
    return 0;
}
2023/6/5 20:46
加载中...