3219. Minimum Cost for Cutting Cake II

There is an m x n cake that needs to be cut into 1 x 1 pieces.

You are given integers m, n, and two arrays:

• horizontalCut of size m - 1, where horizontalCut[i] represents the cost to cut along the horizontal line i.
• verticalCut of size n - 1, where verticalCut[j] represents the cost to cut along the vertical line j.

In one operation, you can choose any piece of cake that is not yet a 1 x 1 square and perform one of the following cuts:

1. Cut along a horizontal line i at a cost of horizontalCut[i].
2. Cut along a vertical line j at a cost of verticalCut[j].

After the cut, the piece of cake is divided into two distinct pieces.

The cost of a cut depends only on the initial cost of the line and does not change.

Return the minimum total cost to cut the entire cake into 1 x 1 pieces.

class Solution {
public:
    long long minimumCost(int n, int m, vector<int>& A, vector<int>& B) {
        sort(begin(A), end(A));
        sort(begin(B), end(B));
        long long res = 0, opa = 1, opb = 1;
        while(A.size() and B.size()) {
            if(A.back() > B.back()) {
                res += A.back() * opb;
                opa++;
                A.pop_back();
            } else {
                res += B.back() * opa;
                opb++;
                B.pop_back();
            }
        }
        return res + accumulate(begin(A), end(A),0ll) * opb + accumulate(begin(B), end(B),0ll) * opa;
    }
};