Submission #13988

#	Time	Username	Problem	Language	Result	Execution time	Memory
13988		kriii	Be Two Bees (OJUZ10_b2b)	C++14	0 / 100	59 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;
rat a(2*1e11,1); int p,q;

void put(int i, int j)
{
	if (i > j) swap(i,j);
	rat n((S-H[i]-H[j])*T[i]*T[j],T[i]+T[j]);
	if (n < a){
		a = n;
		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 / 11
• Subtask 2: 0 / 22
• Subtask 3: 0 / 28
• Subtask 4: 0 / 39