Subtask 1:

Ta có thể dễ dàng đưa subtask này về bài toán "tìm điểm ~x~ sao cho tổng khoảng cách của ~x~ tới các điểm ~a_1, a_2, \ldots, a_n~ là nhỏ nhất có thể". Đây là bài toán cổ điển, với đáp án là đặt ~x~ thành trung vị của mảng ~a~.

Subtask 2:

Ở subtask này, ta có thể đưa về giống subtask 1 như sau: cho tập các điểm ~b~ sao cho điểm ~a_i~ xuất hiện trong tập ~c_i~ lần, ta lại tìm điểm ~x~ sao cho tổng khoảng cách của ~x~ tới các điểm trong tập ~b~ là nhỏ nhất có thể. Ta lại quan tâm tới việc tìm trung vị của tập ~b~, điều này có thể thực hiện được bằng việc chặt nhị phân đáp án, hoặc duyệt qua các giá trị của ~a~ từ bé tới lớn và lưu lại số lần xuất hiện của các giá trị bé hơn tính tới giá trị ~a_i~ đang duyệt qua.

Subtask 3:

Dễ dàng nhận ra rằng đáp án là ~-\infty~ khi và chỉ khi ~\sum_{i=1}^n c_i < 0~.

Giả sử ta đã sắp xếp mảng ~a~ tăng dần. Nhận thấy biểu thức cần tính là một hàm tuyến tính trên từng đoạn ~(-\infty, a_1), [a_1, a_2), [a_2, a_3), \ldots, [a_n, \infty)~. Ngoài ra, ta còn có một số nhận xét sau:

• Trên đoạn ~(-\infty, a_1)~, biểu thức có dạng ~(-\sum_{i=1}^n c_i) x + (\sum_{i=1}^n c_i a_i)~.

• Nếu biểu thức trên đoạn ~[a_{i - 1}, a_i)~ có dạng ~mx + n~, thì qua đoạn ~[a_i, a_{i + 1})~ biểu thức sẽ biến thành ~(m + 2c_i)x + (n - 2c_ia_i)~ (vì hàm ~c_i \cdot |a_i - x|~ chuyển đổi từ ~-c_i x + c_i a_i~ thành ~c_i x - c_i a_i~).

Vì thế, ta có thể duy trì hàm tuyến tính trên từng đoạn ~[a_i, a_{i + 1})~, rồi lấy giá trị nhỏ nhất ở từng đầu mút ~a_i~. Độ phức tạp của thuật toán là ~O(n \log n)~.

#include <bits/stdc++.h>
using namespace std;

const int64_t INF = 1E18;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector<int> a(n), c(n);
        // store px + q as current function
        int64_t p = 0, q = 0;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        map<int, int64_t> pos;
        for (int i = 0; i < n; i++) {
            cin >> c[i];
            // function is -cx + ac
            p -= c[i]; q += 1LL * a[i] * c[i];
            pos[a[i]] += 2 * c[i];
        }
        int64_t ans = INF;
        if (p > 0) {
            ans = -INF;
        }
        for (auto [x, v] : pos) {
            ans = min<int64_t>(ans, 1LL * p * x + q);
            p += v; q -= 1LL * x * v;
        }
        if (p < 0) {
            ans = -INF;
        }
        if (ans == -INF) {
            cout << "-inf\n";
        } else {
            cout << ans << '\n';
        }
    }
}