【題解】Kattis – Traveling Monk

#include <iostream>
#include <iomanip>
using namespace std;

int a, d, h, ah[5005], at[5005], dh[5005], dt[5005];
double mx, mn, now;

bool Check(double num){
    double x = 0, y = 0;
    double n = num;
    for (int i = 0; i < a; i++){
        if (n >= (double)at[i]){
            n -= at[i];
            x += ah[i];
        }
        else if (n){
            x += n/(double)at[i]*ah[i];
            break;
        }
    }
    n = num;
    for (int i = 0; i < d; i++){
        if (n >= (double)dt[i]){
            n -= dt[i];
            y += dh[i];
        }
        else if (n){
            y += n/(double)dt[i]*dh[i];
            break;
        }
    }
    if (x + y >= (double)h) return true;
    return false;
}

int main() {
    cin >> a >> d;
    for (int i = 0; i < a; i++){
        cin >> ah[i] >> at[i];
        h += ah[i];
    }
    for (int i = 0; i < d; i++){
        cin >> dh[i] >> dt[i];
    }
    mn = -1;
    mx = 500005;
    while (mx-mn > 1e-7){
        now = (mx+mn)/2;
        if (Check(now)) mx = now;
        else mn = now;
    }
    cout << fixed << setprecision(6) << mx << "\n";
}