oj.uz

Submission #14145

# Submission time Handle Problem Language Result Execution time Memory
14145 2015-05-02T08:38:02 Z gs13105 Be Two Bees (OJUZ10_b2b) C++
100 / 100
 789 ms 3036 KB 
#include <stdio.h>
#include <algorithm>
 
int h[100000];
int t[100000];
double f[100000];
int arr[100000];
const double EPS=1e-8;
 
inline bool cmp(const int& a, const int& b)
{
    return f[a]>f[b];
}
 
int main()
{
    int r1, r2, n, b, i, j;
    double m=0, s=0, g=500000000000000.0, x;
    scanf("%d", &n);
    for(i=0;i<n;i++)
        scanf("%d", &h[i]);
    for(i=0;i<n;i++)
        scanf("%d", &t[i]);
    for(i=0;i<n;i++)
        m+=h[i];
    if(n<=1000)
    {
        double mn=500000000000000.0, c;
        for(i=0;i<n;i++)
        {
            for(j=i+1;j<n;j++)
            {
                c=(m-h[i]-h[j])/(1.0/t[i]+1.0/t[j]);
                if(c<mn)
                {
                    mn=c;
                    r1=i;
                    r2=j;
                }
            }
        }
        printf("%d %d", r1+1, r2+1);
        return 0;
    }
 
 
    for(b=0;b<40&&s+EPS<g;b++)
    {
        x=(s+g)/2;
        for(i=0;i<n;i++)
        {
            arr[i]=i;
            f[i]=x/t[i]+h[i];
        }
        std::sort(arr, arr+n,cmp);
        if(f[arr[0]]+f[arr[1]]>=m)
        {
            r1=std::min(arr[0], arr[1]);
            r2=std::max(arr[0], arr[1]);
            g=x;
        }
        else
            s=x;
    }
    printf("%d %d", r1+1, r2+1);
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3036 KB Output is correct
2 Correct 0 ms 3036 KB Output is correct
3 Correct 0 ms 3036 KB Output is correct
4 Correct 0 ms 3036 KB Output is correct
5 Correct 0 ms 3036 KB Output is correct
6 Correct 0 ms 3036 KB Output is correct
7 Correct 0 ms 3036 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3036 KB Output is correct
2 Correct 11 ms 3036 KB Output is correct
3 Correct 10 ms 3036 KB Output is correct
4 Correct 0 ms 3036 KB Output is correct
5 Correct 10 ms 3036 KB Output is correct
6 Correct 10 ms 3036 KB Output is correct
7 Correct 10 ms 3036 KB Output is correct
8 Correct 0 ms 3036 KB Output is correct
9 Correct 11 ms 3036 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 3036 KB Output is correct
2 Correct 343 ms 3036 KB Output is correct
3 Correct 788 ms 3036 KB Output is correct
4 Correct 735 ms 3036 KB Output is correct
5 Correct 773 ms 3036 KB Output is correct
6 Correct 781 ms 3036 KB Output is correct
7 Correct 305 ms 3036 KB Output is correct
8 Correct 222 ms 3036 KB Output is correct
9 Correct 418 ms 3036 KB Output is correct
10 Correct 518 ms 3036 KB Output is correct
11 Correct 782 ms 3036 KB Output is correct
12 Correct 612 ms 3036 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 780 ms 3036 KB Output is correct
2 Correct 787 ms 3036 KB Output is correct
3 Correct 780 ms 3036 KB Output is correct
4 Correct 786 ms 3036 KB Output is correct
5 Correct 784 ms 3036 KB Output is correct
6 Correct 558 ms 3036 KB Output is correct
7 Correct 524 ms 3036 KB Output is correct
8 Correct 780 ms 3036 KB Output is correct
9 Correct 789 ms 3036 KB Output is correct
10 Correct 787 ms 3036 KB Output is correct
11 Correct 785 ms 3036 KB Output is correct
12 Correct 784 ms 3036 KB Output is correct
13 Correct 782 ms 3036 KB Output is correct
14 Correct 522 ms 3036 KB Output is correct
15 Correct 424 ms 3036 KB Output is correct
16 Correct 106 ms 3036 KB Output is correct
17 Correct 529 ms 3036 KB Output is correct