oj.uz

Submission #14039

# Submission time Handle Problem Language Result Execution time Memory
14039 2015-04-25T15:01:06 Z kriii Be Two Bees (OJUZ10_b2b) C++14
67 / 100
 69 ms 6840 KB 
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

struct rat{
	rat(){a = 0; b = 1;}
	rat(long long a_, long long b_){
		a = a_; b = b_;
	}
	long long a,b;
	bool operator <(const rat t) const{
		return a * t.b < b * t.a;
	}
};

vector<pair<int, int> > line[100010];
int N,H[100010],T[100010],V[100010],Z; long long S;
int p=-1,q=-1; long long A[5],B[5];

void mul(long long *x, long long p)
{
	for (int i=0;i<5;i++) x[i] *= p;
	for (int i=0;i<5;i++){
		if (x[i] >= 10000000){
			x[i+1] += x[i] / 10000000;
			x[i] %= 10000000;
		}
	}
}

void put(int i, int j)
{
	if (i > j) swap(i,j);
	if (p == -1){
		p = i; q = j;
		return;
	}
	for (int k=0;k<5;k++) A[k] = B[k] = 0;
	A[0] = B[0] = 1;
	mul(A,S-H[i]-H[j]);
	mul(A,T[i]);
	mul(A,T[j]);
	mul(B,T[i]+T[j]);
	mul(B,S-H[p]-H[q]);
	mul(B,T[p]);
	mul(B,T[q]);
	mul(A,T[p]+T[q]);

	bool good = false;
	for (int k=4;k>=0;k--){
		if (A[k] < B[k]){
			good = true;
			break;
		}
		if (A[k] > B[k]) break;
	}
	if (good){
		p = i; q = j;
	}
}

bool bad(long long t1, long long h1, long long t2, long long h2, long long t3, long long h3)
{
	return t2 * t3 * (h2 - h3) + t3 * t1 * (h3 - h1) + t1 * t2 * (h1 - h2) >= t1 * t2 * t3;
}

int main()
{
	scanf ("%d",&N);
	for (int i=0;i<N;i++) scanf ("%d",&H[i]), S += H[i];
	for (int j=0;j<N;j++) scanf ("%d",&T[j]), line[T[j]].push_back(make_pair(H[j],j));

	for (int i=100000;i>=1;i--) if (!line[i].empty()){
		sort(line[i].rbegin(),line[i].rend());
		if (line[i].size() >= 2){
			put(line[i][0].second,line[i][1].second);
		}

		int x = line[i][0].second;
		while (Z >= 2){
			if (bad(T[V[Z-2]],H[V[Z-2]],T[V[Z-1]],H[V[Z-1]],T[x],H[x])){
				put(V[--Z],x);
			}
			else break;
		}
		V[Z++] = x;
		if (Z >= 2){
			put(V[Z-2],V[Z-1]);
		}
	}

	printf ("%d %d\n",p+1,q+1);

	return 0;
}

Subtask #1
0.0 / 11.0

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

Subtask #2
0.0 / 22.0

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

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 5784 KB Output is correct
2 Correct 26 ms 6268 KB Output is correct
3 Correct 15 ms 4992 KB Output is correct
4 Correct 19 ms 5256 KB Output is correct
5 Correct 25 ms 6268 KB Output is correct
6 Correct 33 ms 5920 KB Output is correct
7 Correct 37 ms 5784 KB Output is correct
8 Correct 28 ms 5388 KB Output is correct
9 Correct 43 ms 5652 KB Output is correct
10 Correct 20 ms 5388 KB Output is correct
11 Correct 30 ms 5784 KB Output is correct
12 Correct 42 ms 5784 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 5904 KB Output is correct
2 Correct 69 ms 6708 KB Output is correct
3 Correct 22 ms 5652 KB Output is correct
4 Correct 36 ms 6180 KB Output is correct
5 Correct 55 ms 6840 KB Output is correct
6 Correct 56 ms 6708 KB Output is correct
7 Correct 69 ms 6708 KB Output is correct
8 Correct 50 ms 6840 KB Output is correct
9 Correct 62 ms 6840 KB Output is correct
10 Correct 41 ms 6048 KB Output is correct
11 Correct 37 ms 5924 KB Output is correct
12 Correct 21 ms 5652 KB Output is correct
13 Correct 58 ms 6840 KB Output is correct
14 Correct 63 ms 6708 KB Output is correct
15 Correct 24 ms 5652 KB Output is correct
16 Correct 32 ms 6048 KB Output is correct
17 Correct 55 ms 6708 KB Output is correct