solution

対数を取ると入力は直線なのでconvex hull trick。$O(N)$。

note

式を見たら対数を取りたくなるはずだし取った結果を見るとCHTしたくなるはず。 「そのとき最も性能の高いパソコン」が複数あるとき実装がすこし手間だがまあやればできます。 私は諸々でたくさんバグらせました。

implementation

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define ALL(x) begin(x), end(x)
using namespace std;

constexpr double eps = 1e-12;

struct convex_hull_trick_with_monotonicity {
    convex_hull_trick_with_monotonicity() {
        last_x = - INFINITY;
    }
    void add_line(double a, double b, int label) {
        assert (lines.empty() or get<0>(lines.back()) > a - eps);  // weakly monotonically decreasing
        while (lines.size() >= 2 and not is_required(*(lines.end() - 2), lines.back(), make_tuple( a, b, label ))) {
            lines.pop_back();
        }
        lines.emplace_back(a, b, label);
    }
    vector<int> get_min_labels(double x) {
        assert (last_x < x + eps); last_x = x;  // weakly monotonically increasing
        while (lines.size() >= 2 and get_value(0, x) > get_value(1, x) + eps) {
            lines.pop_front();
        }
        double value = get_value(0, x);
        vector<int> labels;
        REP (i, lines.size()) {
            if (get_value(i, x) > value + eps) break;
            labels.push_back(get<2>(lines[i]));
        }
        return labels;
    }
private:
    typedef tuple<double, double, int> line_t;
    bool is_required(line_t f1, line_t f2, line_t f3) {
        double f1a, f1b; tie(f1a, f1b, ignore) = f1;
        double f2a, f2b; tie(f2a, f2b, ignore) = f2;
        double f3a, f3b; tie(f3a, f3b, ignore) = f3;
        return (f2a - f1a) * (f3b - f2b) < (f2b - f1b) * (f3a - f2a) + eps;
    }
    double get_value(int i, double x) {
        double a, b; tie(a, b, ignore) = lines[i];
        return a * x + b;
    }
    deque<line_t> lines;
    double last_x;  // for the assertion
};

int main() {
    // read curves as lines
    int n; cin >> n;
    vector<double> a(n), b(n);  // in log space
    REP (i, n) {
        int a0, b0, r0; cin >> a0 >> b0 >> r0;
        while (r0 and a0 % b0 == 0) {
            -- r0;
            a0 /= b0;  // to normalize
        }
        a[i] = log(b0);
        b[i] = log(a0) - r0 * log(b0);
    }

    // do CHT
    convex_hull_trick_with_monotonicity cht;
    deque<int> order(n);
    iota(ALL(order), 0);
    sort(ALL(order), [&](int i, int j) { return make_pair(a[i], b[i]) < make_pair(a[j], b[j]); });
    map<pair<double, double>, int> index;
    vector<int> count(n);
    for (int i : order) {
        auto key = make_pair(a[i], b[i]);
        if (not index.count(key)) {
            index[key] = i;
            cht.add_line(- a[i], - b[i], i);  // negate
        }
        ++ count[index[key]];
    }

    // serve queries
    vector<int> used(n);
    int k; cin >> k;
    while (k --) {
        int y; cin >> y;
        vector<int> argmax = cht.get_min_labels(y);
        sort(ALL(argmax), [&](int i, int j) { return a[i] < a[j]; });
        for (int i : argmax) {
            if (used[i] < count[i]) {
                ++ used[i];
                break;
            }
        }
    }

    // output
    int answer = accumulate(ALL(used), 0);
    cout << answer << endl;
    return 0;
}