#include<stdio.h>
#include<algorithm>
using namespace std;
int n, p1, p2;
double P[101000];
struct A{
int h, t;
}w[101000];
bool Pos(double K){
int i, x1 = -1, x2 = -1, t;
double Mx1=0, Mx2=0, S = 0;
for (i = 0; i < n; i++){
P[i] = w[i].h + (1.0 / w[i].t)*K;
S += w[i].h;
}
for (i = 0; i < n; i++){
if (x1 == -1 || Mx1 < P[i]){
Mx2 = Mx1; Mx1 = P[i];
x2 = x1; x1 = i;
}
else if (x2 == -1 || Mx2 < P[i])Mx2 = P[i], x2 = i;
}
if (S <= Mx1 + Mx2){
p1 = x1, p2 = x2;
return true;
}
return false;
}
int main(){
int i;
scanf("%d", &n);
for (i = 0; i < n; i++)scanf("%d", &w[i].h);
for (i = 0; i < n; i++)scanf("%d", &w[i].t);
double bb, ee, mid;
bb = 0.1, ee = 1e17;
while (ee-bb > 1e-5){
mid = (bb + ee)*0.5;
if (Pos(mid)){
ee = mid;
}
else bb = mid;
}
if (p1 > p2)swap(p1, p2);
printf("%d %d\n", p1 + 1, p2 + 1);
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
2660 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2660 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2660 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2660 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2660 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2660 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2660 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
2660 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2660 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2660 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2660 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2660 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2660 KB |
Output is correct |
| 7 |
Execution timed out |
1000 ms |
2656 KB |
Program timed out |
| 8 |
Correct |
0 ms |
2660 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2660 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1000 ms |
2656 KB |
Program timed out |
| 2 |
Correct |
124 ms |
2660 KB |
Output is correct |
| 3 |
Correct |
75 ms |
2660 KB |
Output is correct |
| 4 |
Correct |
40 ms |
2660 KB |
Output is correct |
| 5 |
Correct |
123 ms |
2660 KB |
Output is correct |
| 6 |
Correct |
71 ms |
2660 KB |
Output is correct |
| 7 |
Correct |
117 ms |
2660 KB |
Output is correct |
| 8 |
Correct |
69 ms |
2660 KB |
Output is correct |
| 9 |
Correct |
116 ms |
2660 KB |
Output is correct |
| 10 |
Correct |
114 ms |
2660 KB |
Output is correct |
| 11 |
Correct |
123 ms |
2660 KB |
Output is correct |
| 12 |
Execution timed out |
1000 ms |
2656 KB |
Program timed out |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1000 ms |
2656 KB |
Program timed out |
| 2 |
Correct |
123 ms |
2660 KB |
Output is correct |
| 3 |
Execution timed out |
1000 ms |
2656 KB |
Program timed out |
| 4 |
Correct |
130 ms |
2660 KB |
Output is correct |
| 5 |
Execution timed out |
1000 ms |
2656 KB |
Program timed out |
| 6 |
Execution timed out |
1000 ms |
2656 KB |
Program timed out |
| 7 |
Execution timed out |
1000 ms |
2656 KB |
Program timed out |
| 8 |
Correct |
86 ms |
2660 KB |
Output is correct |
| 9 |
Execution timed out |
1000 ms |
2656 KB |
Program timed out |
| 10 |
Execution timed out |
1000 ms |
2656 KB |
Program timed out |
| 11 |
Correct |
129 ms |
2660 KB |
Output is correct |
| 12 |
Correct |
73 ms |
2660 KB |
Output is correct |
| 13 |
Execution timed out |
1000 ms |
2656 KB |
Program timed out |
| 14 |
Correct |
125 ms |
2660 KB |
Output is correct |
| 15 |
Correct |
86 ms |
2660 KB |
Output is correct |
| 16 |
Correct |
122 ms |
2660 KB |
Output is correct |
| 17 |
Execution timed out |
1000 ms |
2656 KB |
Program timed out |
