Submission #19117

#	Time	Username	Problem	Language	Result	Execution time	Memory
19117		tlwpdus	Be Two Bees (OJUZ10_b2b)	C++98	100 / 100	945 ms	2648 KiB

b2b

#include<stdio.h>
#include<algorithm>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;
#define h first
#define t second

const ll INF = 1LL<<60;

int n;
pll arr[100100];
double x;
ll S;

bool cmp(pll a, pll b) {
	return x/a.t+a.h<x/b.t+b.h;
}

pll m1, m2;
int t1, t2;
bool ok() {
	m1=pll(-1000000,1000000), m2 = pll(-1000000,1000000);
	int i;
	for (i=0;i<n;i++) {
		if (cmp(m1,arr[i])) m2=m1,m1=arr[i],t2=t1,t1=i;
		else if (cmp(m2,arr[i])) m2=arr[i],t2=i;
	}
	return (double)(S-m1.h-m2.h)/(1.0/m1.t+1.0/m2.t)<=x;
}

void process() {
	int i;
	double s = 0, e = INF;
	for (i=0;i<300;i++) {
		x = (s+e)/2;
		if (ok()) e=x;
		else s=x;
	}
	printf("%d %d\n",min(t1,t2)+1,max(t1,t2)+1);
}

void input() {
	int i;
	scanf("%d",&n);
	for (i=0;i<n;i++) scanf("%lld",&arr[i].h), S += arr[i].h;
	for (i=0;i<n;i++) scanf("%lld",&arr[i].t);
}

int main() {
	input();
	process();
	return 0;
}

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