1class Solution {
2    /**
3     * Computes the minimum total time for all potions to be processed through
4     * a sequence of wizards (a flow-shop scheduling problem).
5     *
6     * Each potion j must pass through every wizard i in order. The time wizard i
7     * spends on potion j is skill[i] * mana[j]. A wizard can only start a potion
8     * after finishing the previous potion AND after the previous wizard has
9     * finished that same potion (no waiting allowed between wizards once started).
10     *
11     * @param skill the processing factor of each wizard, in order
12     * @param mana  the size of each potion, in processing order
13     * @return the finish time of the last potion at the last wizard
14     */
15    public long minTime(int[] skill, int[] mana) {
16        int wizardCount = skill.length;
17
18        // finishTime[i] holds the time at which wizard i finishes the
19        // potion currently being tracked.
20        long[] finishTime = new long[wizardCount];
21
22        // Process each potion in the given order.
23        for (int potion : mana) {
24            long currentTime = 0;
25
26            // Forward pass: compute the finish time at each wizard for this potion.
27            // A wizard can only begin after both:
28            //   (1) it has finished its previous potion (finishTime[i]), and
29            //   (2) the running cumulative time so far (currentTime).
30            for (int i = 0; i < wizardCount; ++i) {
31                currentTime = Math.max(currentTime, finishTime[i]) + (long) skill[i] * potion;
32            }
33
34            // The last wizard's finish time for this potion is fixed.
35            finishTime[wizardCount - 1] = currentTime;
36
37            // Backward pass: since the potion flows continuously without gaps,
38            // back-calculate each earlier wizard's finish time by subtracting
39            // the processing time of the next wizard for this potion.
40            for (int i = wizardCount - 2; i >= 0; --i) {
41                finishTime[i] = finishTime[i + 1] - (long) skill[i + 1] * potion;
42            }
43        }
44
45        // The answer is when the last wizard finishes the last potion.
46        return finishTime[wizardCount - 1];
47    }
48}
49

1class Solution {
2public:
3    long long minTime(vector<int>& skill, vector<int>& mana) {
4        int numWizards = skill.size();
5
6        // finishTime[i] records the time at which potion currently being
7        // processed leaves wizard i (i.e., finishes at wizard i).
8        vector<long long> finishTime(numWizards);
9
10        // Process each potion in order; potions cannot overtake one another,
11        // so they form a strict pipeline through the wizards.
12        for (int currentMana : mana) {
13            long long runningTime = 0;
14
15            // Forward pass: push the current potion through all wizards.
16            // At each wizard the potion can only start once both:
17            //   1) the previous potion has left this wizard (finishTime[i]), and
18            //   2) this potion has finished at the previous wizard (runningTime).
19            // We then add the brewing cost skill[i] * currentMana.
20            for (int i = 0; i < numWizards; ++i) {
21                runningTime = max(runningTime, finishTime[i]) + 1LL * skill[i] * currentMana;
22            }
23
24            // The last wizard's finish time is the running total.
25            finishTime[numWizards - 1] = runningTime;
26
27            // Backward pass: reconstruct each wizard's finish time for this
28            // potion by subtracting the brewing cost of the next wizard.
29            // Since the potion flows continuously without gaps once started,
30            // finishTime[i] = finishTime[i + 1] - cost incurred at wizard (i + 1).
31            for (int i = numWizards - 2; i >= 0; --i) {
32                finishTime[i] = finishTime[i + 1] - 1LL * skill[i + 1] * currentMana;
33            }
34        }
35
36        // After all potions are processed, the answer is when the last potion
37        // leaves the final wizard.
38        return finishTime[numWizards - 1];
39    }
40};
41

1/**
2 * Compute the minimum total time to process all potions through all labs,
3 * where each potion must pass through labs in order without gaps,
4 * and each lab processes potions in the given order.
5 *
6 * @param skill - Time multipliers for each lab (length n).
7 * @param mana  - Mana values for each potion (length m).
8 * @returns The earliest time the last potion finishes at the last lab.
9 */
10function minTime(skill: number[], mana: number[]): number {
11    // Number of labs.
12    const labCount: number = skill.length;
13
14    // finishTime[i] holds the time at which the current potion
15    // leaves lab i (i.e., finishes processing there).
16    const finishTime: number[] = Array(labCount).fill(0);
17
18    // Process each potion in order.
19    for (const currentMana of mana) {
20        // Forward pass: determine when this potion finishes at the last lab.
21        // At each lab, the potion can only start after the lab is free
22        // (Math.max with the lab's previous finish time), then it spends
23        // skill[i] * currentMana time there.
24        let runningTime: number = 0;
25        for (let i = 0; i < labCount; ++i) {
26            runningTime = Math.max(runningTime, finishTime[i]) + skill[i] * currentMana;
27        }
28
29        // The computed runningTime is the finish time at the last lab.
30        finishTime[labCount - 1] = runningTime;
31
32        // Backward pass: back-fill the finish times for earlier labs so they
33        // align tightly with the last lab (no idle waiting for this potion).
34        // The potion must flow continuously, so lab i finishes exactly
35        // skill[i + 1] * currentMana before lab i + 1.
36        for (let i = labCount - 2; i >= 0; --i) {
37            finishTime[i] = finishTime[i + 1] - skill[i + 1] * currentMana;
38        }
39    }
40
41    // The last lab's finish time after the final potion is the answer.
42    return finishTime[labCount - 1];
43}
44