2398. Maximum Number of Robots Within Budget

You have n robots. You are given two 0-indexed integer arrays, chargeTimes and runningCosts, both of length n. The ith robot costs chargeTimes[i] units to charge and costs runningCosts[i] units to run. You are also given an integer budget.

The total cost of running k chosen robots is equal to max(chargeTimes) + k * sum(runningCosts), where max(chargeTimes) is the largest charge cost among the k robots and sum(runningCosts) is the sum of running costs among the k robots.

Return the maximum number of consecutive robots you can run such that the total cost does not exceed budget.

class Solution {
public:
    int maximumRobots(vector<int>& C, vector<int>& R, long long B) {
        long long res = 0, l = 0, r = 0, n = C.size(), now = 0;
        priority_queue<pair<long long, long long>> Q;
        auto eval = [&]() {return (Q.empty() ? 0 : Q.top().first) + (r - l) * now <= B;};
        while(r < n) {
            while(!Q.empty() and Q.top().second < l) Q.pop();
            while(r < n and eval()) {
                res = max(res, r - l);
                Q.push({C[r],r});
                now += R[r];
                r++;
            }
            if(eval()) res = max(res, r - l);
            while(r < n and l < r and !eval()) {
                now -= R[l++];
                while(!Q.empty() and Q.top().second < l) Q.pop();
            }
        }
        return res;
    }
};