Submission #19116

#	Time	Username	Problem	Language	Result	Execution time	Memory
19116		tlwpdus	Be Two Bees (OJUZ10_b2b)	C++98	0 / 100	190 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];
ll x;
ll S;

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

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 (S-m1.h-m2.h)*m1.t*m2.t<=(m1.t+m2.t)*x;
}

void process() {
	int i;
	ll 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: 0 / 11
• Subtask 2: 0 / 22
• Subtask 3: 0 / 28
• Subtask 4: 0 / 39