4009. Minimum Possible Maximum Waiting Time

You are given an integer array demand, where demand[i] is the amount of fuel required by the i^th car.

You are also given an integer array fuel of length 2. There are exactly two fuel dispensers, numbered 0 and 1, where fuel[j] is the initial amount of fuel available in dispenser j.

Cars are allowed to start refueling in increasing index order. Car 0 becomes allowed at time 0, and for each i > 0, car i becomes allowed exactly when car i - 1 starts refueling.

The refueling process follows these rules:

• Each dispenser can serve at most one car at a time.
• When a car becomes allowed, you must choose a dispenser with at least demand[i] fuel remaining. If both dispensers have enough fuel remaining, you may choose either of them, regardless of when they become free.
• The car waits until the chosen dispenser becomes free and starts refueling immediately. It cannot switch dispensers or intentionally wait after the chosen dispenser becomes free.
• When a car starts refueling, the remaining fuel in the chosen dispenser decreases by demand[i], and the dispenser remains occupied for demand[i] seconds.
• Once started, refueling cannot be interrupted.
• If neither dispenser has at least demand[i] fuel remaining when car i becomes allowed, the process terminates and no further cars can be served.

The waiting time of a car is the time between when it becomes allowed to start refueling and when it actually starts.

Return the minimum possible value of the maximum waiting time among all served cars over all assignments that maximize the number of served cars. If no car can be served, return -1.

class Solution {
    int INF = 1e9;
    int states = 51 * 21 * 21;

    int encode(int f1, int t1, int t2) {
        return (f1 * 21 + t1) * 21 + t2;
    }

    array<int, 4> decode(int state, int fuelSum, int usedFuel) {
        int t2 = state % 21;
        state /= 21;

        int t1 = state % 21;
        int f1 = state / 21;
        int f2 = fuelSum - usedFuel - f1;

        return {f1, f2, t1, t2};
    }

public:
    int minMaxWaitingTime(vector<int>& demand, vector<int>& fuel) {
        if(demand[0] > max(fuel[0], fuel[1])) return -1;
        vector<int> dp(states, INF), dpp(states, INF);
        vector<int> cur, nxt;

        int fuelSum = fuel[0] + fuel[1];
        int usedFuel = 0;

        int initialState = encode(fuel[0], 0, 0);
        dp[initialState] = 0;
        cur.push_back(initialState);

        for(int idx = 0; idx < demand.size(); idx++) {
            fill(dpp.begin(), dpp.end(), INF);
            nxt.clear();

            int d = demand[idx];

            for(int state : cur) {
                auto [f1, f2, t1, t2] = decode(
                        state,
                        fuelSum,
                        usedFuel
                );

                if(f1 >= d) {
                    int nextState = encode(f1 - d,d,max(0, t2 - t1));
                    int nextWait = max(dp[state], t1);
                    if(dpp[nextState] == INF) {
                        nxt.push_back(nextState);
                    }

                    dpp[nextState] = min(dpp[nextState], nextWait);
                }

                if(f2 >= d) {
                    int nextState = encode(f1,max(0, t1 - t2),d);
                    int nextWait = max(dp[state], t2);
                    if(dpp[nextState] == INF) {
                        nxt.push_back(nextState);
                    }

                    dpp[nextState] = min(dpp[nextState], nextWait);
                }
            }

            if(nxt.empty()) break;
            usedFuel += d;
            dp.swap(dpp);
            cur.swap(nxt);
        }

        int res = INF;
        for(int state : cur) res = min(res, dp[state]);
        return res;
    }
};