Submission #14041

#	Time	Username	Problem	Language	Result	Execution time	Memory
14041		kriii	Be Two Bees (OJUZ10_b2b)	C++14	100 / 100	82 ms	6840 KiB

b2b

#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]);

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

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: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 28 / 28
• Subtask 4: 39 / 39