oj.uz

Submission #13988

# Submission time Handle Problem Language Result Execution time Memory
13988 2015-04-24T18:23:19 Z kriii Be Two Bees (OJUZ10_b2b) C++14
0 / 100
 59 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;
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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 4728 KB Output isn't correct
2 Correct 0 ms 4728 KB Output is correct
3 Correct 0 ms 4728 KB Output is correct
4 Correct 1 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 Incorrect 0 ms 4728 KB Output isn't 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 Incorrect 0 ms 4728 KB Output isn't correct
7 Correct 0 ms 4728 KB Output is correct
8 Correct 0 ms 4728 KB Output is correct
9 Correct 0 ms 4728 KB Output is correct

Subtask #3
0.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 5784 KB Output is correct
2 Correct 29 ms 5784 KB Output is correct
3 Correct 33 ms 5784 KB Output is correct
4 Correct 30 ms 6268 KB Output is correct
5 Correct 20 ms 6268 KB Output is correct
6 Correct 15 ms 5256 KB Output is correct
7 Correct 39 ms 5920 KB Output is correct
8 Correct 13 ms 4992 KB Output is correct
9 Correct 22 ms 5388 KB Output is correct
10 Correct 23 ms 5388 KB Output is correct
11 Incorrect 33 ms 5652 KB Output isn't correct
12 Correct 35 ms 5784 KB Output is correct

Subtask #4
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 6840 KB Output is correct
2 Correct 48 ms 6708 KB Output is correct
3 Correct 56 ms 6708 KB Output is correct
4 Incorrect 27 ms 5924 KB Output isn't correct
5 Correct 53 ms 6840 KB Output is correct
6 Correct 31 ms 5652 KB Output is correct
7 Correct 35 ms 6708 KB Output is correct
8 Correct 30 ms 6180 KB Output is correct
9 Correct 34 ms 6840 KB Output is correct
10 Incorrect 33 ms 5904 KB Output isn't correct
11 Correct 52 ms 6048 KB Output is correct
12 Correct 44 ms 6708 KB Output is correct
13 Incorrect 40 ms 6048 KB Output isn't correct
14 Correct 59 ms 6840 KB Output is correct
15 Incorrect 9 ms 5652 KB Output isn't correct
16 Correct 28 ms 5652 KB Output is correct
17 Correct 50 ms 6708 KB Output is correct