提出 #71734973

---

ソースコード 拡げる

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

using int64 = long long;
using i128  = __int128_t;
static const int64 INF64 = (1LL<<62);

struct Solver {
    int N;
    vector<int64> A; // 2N
    vector<int64> B; // N
    vector<int64> X; // N (upper rows)
    vector<int64> Y; // N (columns)

    vector<int> ord;        // upper rows sorted by X/A
    vector<int64> prefSX;   // prefix sum X along ord
    vector<int64> prefAU;   // prefix sum A(upper) along ord
    vector<int64> lowPref;  // sum of k largest A in lower half
    int64 Atot;

    vector<int> opt_t;         // t*(k)
    vector<int64> best_cost;   // best cost for each k

    Solver(int n,
           vector<int64> A_,
           vector<int64> B_,
           vector<int64> X_,
           vector<int64> Y_)
        : N(n), A(move(A_)), B(move(B_)), X(move(X_)), Y(move(Y_)) {
        build();
    }

    void build() {
        Atot = 0;
        for (auto v: A) Atot += v;

        ord.resize(N);
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](int i, int j){
            // compare X[i]/A[i] < X[j]/A[j] as X[i]*A[j] < X[j]*A[i]
            i128 lhs = (i128)X[i] * (i128)A[j];
            i128 rhs = (i128)X[j] * (i128)A[i];
            if (lhs != rhs) return lhs < rhs;
            return i < j;
        });

        prefSX.assign(N+1, 0);
        prefAU.assign(N+1, 0);
        for (int t = 1; t <= N; t++) {
            int i = ord[t-1];
            prefSX[t] = prefSX[t-1] + X[i];
            prefAU[t] = prefAU[t-1] + A[i];
        }

        vector<int64> lower;
        lower.reserve(N);
        for (int i = N; i < 2*N; i++) lower.push_back(A[i]);
        sort(lower.begin(), lower.end(), greater<int64>());
        lowPref.assign(N+1, 0);
        for (int k = 1; k <= N; k++) lowPref[k] = lowPref[k-1] + lower[k-1];

        opt_t.assign(N+1, 0);
        best_cost.assign(N+1, INF64);
    }

    // D&C optimization with safe SAT/LIN/VAR classification.
    // We pass down only currently-variable columns; fixed contributions are accumulated.
    void dc_opt(int kL, int kR, int tL, int tR,
                const vector<int>& cols,
                i128 satSumB_acc,
                int64 linCnt_acc,
                int64 linSumY_acc) {
        if (kL > kR) return;

        // Safe bounds in this node:
        // k in [kL,kR], S in [SX(tL), SX(tR)]
        int64 Smin = prefSX[tL];
        int64 Smax = prefSX[tR];

        i128 satSumB = satSumB_acc;
        int64 linCnt = linCnt_acc;
        int64 linSumY = linSumY_acc;

        vector<int> varCols;
        varCols.reserve(cols.size());

        for (int j : cols) {
            i128 Amin = (i128)Smin + (i128)kL * (i128)Y[j];
            i128 Amax = (i128)Smax + (i128)kR * (i128)Y[j];

            if (Amin >= (i128)B[j]) {
                // always saturated: contributes Bj
                satSumB += (i128)B[j];
            } else if (Amax < (i128)B[j]) {
                // always linear: contributes S + kYj
                linCnt += 1;
                linSumY += Y[j];
            } else {
                // may change: keep variable
                varCols.push_back(j);
            }
        }

        int mid = (kL + kR) >> 1;

        // ----- Build a structure for VAR at fixed k=mid -----
        int m = (int)varCols.size();
        vector<int64> C(m);
        int64 sumYvar = 0;
        for (int idx = 0; idx < m; idx++) {
            int j = varCols[idx];
            sumYvar += Y[j];
            // min(Bj, S + kYj) = kYj + min(Bj - kYj, S)
            C[idx] = B[j] - 1LL * mid * Y[j];
        }
        sort(C.begin(), C.end());
        vector<i128> prefC(m+1);
        prefC[0] = 0;
        for (int i = 0; i < m; i++) prefC[i+1] = prefC[i] + (i128)C[i];

        // Scan t in [tL..tR] and evaluate cost(mid,t) fast using two-pointer on sorted C.
        int bestT = tL;
        int64 bestV = INF64;
        int p = 0; // count of C <= S

        for (int t = tL; t <= tR; t++) {
            int64 S = prefSX[t];

            while (p < m && C[p] <= S) p++;

            // sum_{var} min(C, S) = prefC[p] + (m-p)*S
            i128 sumMinC = prefC[p] + (i128)(m - p) * (i128)S;

            // phi = sat + lin + var
            // lin: linCnt*S + mid*linSumY
            // var: mid*sumYvar + sumMinC
            i128 phi = satSumB
                     + (i128)linCnt * (i128)S
                     + (i128)mid * (i128)linSumY
                     + (i128)mid * (i128)sumYvar
                     + sumMinC;

            i128 base = (i128)Atot - (i128)prefAU[t] - (i128)lowPref[mid];
            i128 ans128 = base + phi;

            int64 v;
            if (ans128 > (i128)INF64) v = INF64;
            else if (ans128 < (i128)-INF64) v = -INF64;
            else v = (int64)ans128;

            if (v < bestV) {
                bestV = v;
                bestT = t;
            }
        }

        opt_t[mid] = bestT;
        best_cost[mid] = bestV;

        // Recurse; only varCols remain relevant; accumulated (sat, lin) are fixed.
        dc_opt(kL, mid - 1, tL, bestT, varCols, satSumB, linCnt, linSumY);
        dc_opt(mid + 1, kR, bestT, tR, varCols, satSumB, linCnt, linSumY);
    }

    int64 solve() {
        vector<int> allCols(N);
        iota(allCols.begin(), allCols.end(), 0);
        dc_opt(0, N, 0, N, allCols, (i128)0, 0, 0);

        int64 ans = INF64;
        for (int k = 0; k <= N; k++) ans = min(ans, best_cost[k]);
        return ans;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int64> A(2*N), B(N), X(N), Y(N);
    for (int i = 0; i < 2*N; i++) cin >> A[i];
    for (int j = 0; j < N; j++) cin >> B[j];
    for (int i = 0; i < N; i++) cin >> X[i];
    for (int j = 0; j < N; j++) cin >> Y[j];

    Solver solver(N, A, B, X, Y);
    cout << solver.solve() << "\n";
    return 0;
}

提出情報

ジャッジ結果