Submission #19115

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19115	2016-02-18T13:49:15 Z	tlwpdus	Be Two Bees (OJUZ10_b2b)	C++	0 / 100	338 ms	2648 KB

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

0.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	2648 KB	Output isn't correct
2	Incorrect	0 ms	2648 KB	Output isn't correct
3	Correct	0 ms	2648 KB	Output is correct
4	Correct	0 ms	2648 KB	Output is correct
5	Correct	0 ms	2648 KB	Output is correct
6	Correct	0 ms	2648 KB	Output is correct
7	Incorrect	0 ms	2648 KB	Output isn't correct

Subtask #2

0.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2648 KB	Output is correct
2	Correct	4 ms	2648 KB	Output is correct
3	Incorrect	0 ms	2648 KB	Output isn't correct
4	Incorrect	4 ms	2648 KB	Output isn't correct
5	Correct	0 ms	2648 KB	Output is correct
6	Correct	0 ms	2648 KB	Output is correct
7	Correct	0 ms	2648 KB	Output is correct
8	Incorrect	0 ms	2648 KB	Output isn't correct
9	Correct	4 ms	2648 KB	Output is correct

Subtask #3

0.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	331 ms	2648 KB	Output is correct
2	Incorrect	186 ms	2648 KB	Output isn't correct
3	Incorrect	108 ms	2648 KB	Output isn't correct
4	Incorrect	161 ms	2648 KB	Output isn't correct
5	Correct	325 ms	2648 KB	Output is correct
6	Correct	332 ms	2648 KB	Output is correct
7	Incorrect	330 ms	2648 KB	Output isn't correct
8	Correct	192 ms	2648 KB	Output is correct
9	Incorrect	203 ms	2648 KB	Output isn't correct
10	Incorrect	328 ms	2648 KB	Output isn't correct
11	Correct	234 ms	2648 KB	Output is correct
12	Incorrect	331 ms	2648 KB	Output isn't correct

Subtask #4

0.0 / 39.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	334 ms	2648 KB	Output is correct
2	Incorrect	334 ms	2648 KB	Output isn't correct
3	Correct	338 ms	2648 KB	Output is correct
4	Incorrect	332 ms	2648 KB	Output isn't correct
5	Correct	192 ms	2648 KB	Output is correct
6	Correct	331 ms	2648 KB	Output is correct
7	Incorrect	231 ms	2648 KB	Output isn't correct
8	Correct	332 ms	2648 KB	Output is correct
9	Correct	337 ms	2648 KB	Output is correct
10	Correct	328 ms	2648 KB	Output is correct
11	Incorrect	332 ms	2648 KB	Output isn't correct
12	Correct	329 ms	2648 KB	Output is correct
13	Correct	332 ms	2648 KB	Output is correct
14	Correct	233 ms	2648 KB	Output is correct
15	Incorrect	327 ms	2648 KB	Output isn't correct
16	Correct	108 ms	2648 KB	Output is correct
17	Correct	333 ms	2648 KB	Output is correct