Cutting Boards

• Time : O(nlogn + mlogm)
• Space : O(1)

c++

int boardCutting(vector<int> cy, vector<int> cx) {
    long long res = 0, x = 1, y = 1, mod = 1e9 + 7;
    sort(begin(cy), end(cy));
    sort(begin(cx), end(cx));
    while(!cy.empty() and !cx.empty()) {
        long long ycost = x * cy.back(), xcost = y * cx.back();
        if(cy.back() > cx.back()) {
            res = (res + ycost) % mod;
            cy.pop_back();
            y++;
        } else {
            res = (res + xcost) % mod;
            cx.pop_back();
            x++;
        }
    }
    while(!cy.empty()) {
        long long ycost = x * cy.back();
        res = (res + ycost) % mod;
        cy.pop_back();
        y++;
    }
    while(!cx.empty()) {
        long long xcost = y * cx.back();
        res = (res + xcost) % mod;
        cx.pop_back();
        x++;
    }
    return res;
}