제출 #13955

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
13955		imsifile	Be Two Bees (OJUZ10_b2b)	C++98	100 / 100	71 ms	2648 KiB

b2b

#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;
}

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 28 / 28
• Subtask 4: 39 / 39