Submission #13949

#TimeUsernameProblemLanguageResultExecution timeMemory
13949aintaBe Two Bees (OJUZ10_b2b)C++98
11 / 100
1000 ms2660 KiB
#include<stdio.h>
#include<algorithm>
using namespace std;
int n, p1, p2;
double P[101000];
struct A{
	int h, t;
}w[101000];
bool Pos(double K){
	int i, x1 = -1, x2 = -1, t;
	double Mx1=0, Mx2=0, S = 0;
	for (i = 0; i < n; i++){
		P[i] = w[i].h + (1.0 / w[i].t)*K;
		S += w[i].h;
	}
	for (i = 0; i < n; i++){
		if (x1 == -1 || Mx1 < P[i]){
			Mx2 = Mx1; Mx1 = P[i];
			x2 = x1; x1 = i;
		}
		else if (x2 == -1 || Mx2 < P[i])Mx2 = P[i], x2 = i;
	}
	if (S <= Mx1 + Mx2){
		p1 = x1, p2 = x2;
		return true;
	}
	return false;
}
int main(){
	int i;
	scanf("%d", &n);
	for (i = 0; i < n; i++)scanf("%d", &w[i].h);
	for (i = 0; i < n; i++)scanf("%d", &w[i].t);
	double bb, ee, mid;
	bb = 0.1, ee = 1e17;
	while (ee-bb > 1e-6){
		mid = (bb + ee)*0.5;
		if (Pos(mid)){
			ee = mid;
		}
		else bb = mid;
	}
	if (p1 > p2)swap(p1, p2);
	printf("%d %d\n", p1 + 1, p2 + 1);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...