Submission #14145

#	Time	Username	Problem	Language	Result	Execution time	Memory
14145		gs13105	Be Two Bees (OJUZ10_b2b)	C++98	100 / 100	789 ms	3036 KiB

b2b

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