2234. Maximum Total Beauty of the Gardens

Alice is a caretaker of n gardens and she wants to plant flowers to maximize the total beauty of all her gardens.

You are given a 0-indexed integer array flowers of size n, where flowers[i] is the number of flowers already planted in the ith garden. Flowers that are already planted cannot be removed. You are then given another integer newFlowers, which is the maximum number of flowers that Alice can additionally plant. You are also given the integers target, full, and partial.

A garden is considered complete if it has at least target flowers. The total beauty of the gardens is then determined as the sum of the following:

• The number of complete gardens multiplied by full.
• The minimum number of flowers in any of the incomplete gardens multiplied by partial. If there are no incomplete gardens, then this value will be 0.

Return the maximum total beauty that Alice can obtain after planting at most newFlowers flowers.

class Solution {
public:
    long long maximumBeauty(vector<int>& f, long long nf, int ta, int fu, int pa) {
        long long res = 0, n = f.size();
        sort(begin(f), end(f));
        vector<long long> psum(n,f[0]);
        for(int i = 1; i < n; i++) psum[i] = psum[i-1] + f[i];
        f.push_back(INT_MAX);
        for(int i = n; i >= 0; i--) {
            long long req = max(0, ta - f[i]);
            if(nf < req) break;
            nf -= req;
            f.pop_back();
            
            long long satisfy = 1ll * (n - i) * fu, unsatisfy = 0;
            int l = 0, r = ta - 1;
            
            while(l <= r) {
                int m = l + (r - l) / 2;
                auto j = upper_bound(begin(f), end(f), m) - begin(f);
                if(j == 0) l = m + 1;
                else {
                    long long req = m * j - psum[j-1];
                    if(req <= nf) {
                        l = m + 1;
                        unsatisfy = 1ll * m * pa;
                    } else r = m -1;
                }
            }
            
            res = max(res, satisfy + unsatisfy);
        }
        
        return res;
    }
};