Submission #13955

#TimeUsernameProblemLanguageResultExecution timeMemory
13955imsifileBe Two Bees (OJUZ10_b2b)C++98
100 / 100
71 ms2648 KiB
#include<stdio.h> int n, da, db; long long sum, hi[100100], ti[100100]; double mi=0, mx, md; double pick(int a, int b){ double honey=sum-hi[a]-hi[b]; double til=(1.0/ti[a])+(1.0/ti[b]); return honey/til; } bool test(double vl){ double ma=0, mb=0; int i, ia, ib; for(i=0; i<n; i++){ double gp=hi[i]+vl/ti[i]; if(ma<gp)mb=ma, ib=ia, ma=gp, ia=i; else if(mb<gp)mb=gp, ib=i; } if(ma+mb > sum)da=ia, db=ib; return (ma+mb) > sum; } int main(){ int i; scanf("%d", &n); for(i=0; i<n; i++)scanf("%lld", &hi[i]), sum+=hi[i]; for(i=0; i<n; i++)scanf("%lld", &ti[i]); da=0, db=1, mx=pick(0,1); while((mx-mi)/mx > 1e-10){ md=(mi+mx)/2.0; if(test(md))mx=pick(da,db); else mi=md; } if(da>db){ int im=da; da=db, db=im; } printf("%d %d", da+1, db+1); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...