Convoy Load Balancing With Escort Weight - Google Online Assessment

Problem Preview

"Captain Reyes runs a supply convoy along a single desert highway. The crates waiting at base camp are lined up in a fixed order on the loading dock, and that order can never be changed — trucks must scoop up a contiguous run of crates exactly as they sit on the dock. Every truck that heads out also drags a fixed escort trailer, whose weight is added once to whatever load the truck is already carrying. On top of that, dock safety rules cap how many crates a single truck bed may physically hold, regardless of how light those crates are. Reyes has a fixed number of trucks available and must use every single one of them, dividing the full line of crates into that many non-empty contiguous convoys, with no convoy exceeding the crate-count cap. Reyes wants to know the smallest possible value for the heaviest truck's total load (crates plus its escort trailer), if the crates are split as cleverly as possible into that many contiguous, cap-respecting groups. #### Function Description Implement the function `minMaxConvoyLoad`. #### Parameters * `n`: the number of crates on the dock * `k`: the number of trucks that must be used (the dock is split into exactly `k` contiguous non-empty groups) * `escort`: the fixed escort trailer weight added once to every truck's load * `maxCrates`: the maximum number of crates any single truck's group may contain * `weights`: array of `n` integers, the weight of each crate in dock order #### Input Format * Line 1: `n` * Line 2: `k` * Line 3: `escort` * Line 4: `maxCrates` * Line 5: `n` space-separated integers — `weights[0] weights[1] ... weights[n-1]` #### Output Format * A single integer: the minimum possible value of the maximum truck load across all ways to split the crates into exactly `k` contiguous groups, none containing more than `maxCrates` crates. #### Constraints * 1 ≤ k ≤ n ≤ 100,000 * 1 ≤ weights[i] ≤ 10^9 * 0 ≤ escort ≤ 10^9 * 1 ≤ maxCrates ≤ n, and k × maxCrates ≥ n (at least one valid split into exactly k groups exists) All values are integers. --- #### Sample Input 1 ```text 5 2 3 3 4 8 5 6 2 ``` #### Sample Output 1 ```text 16 ``` #### Explanation There are 5 crates with weights 4, 8, 5, 6, and 2. Each truck also carries an escort weight of 3, and each truck can carry at most 3 crates. The crates must be divided into exactly 2 contiguous groups. Since both groups must contain at most 3 crates and together must include all 5 crates, the only possible group-size combinations are 2 crates followed by 3 crates, or 3 crates followed by 2 crates. A split of 1 crate and 4 crates, or 4 crates and 1 crate, is not allowed because one truck would carry more than 3 crates. For the first possible split, the groups are 4, 8 and 5, 6, 2. The first group has a total crate weight of 4 + 8 = 12. After adding the escort weight of 3, the truck load becomes 15. The second group has a total crate weight of 5 + 6 + 2 = 13. After adding the escort weight of 3, the truck load becomes 16. The heavier truck load for this split is 16. For the second possible split, the groups are 4, 8, 5 and 6, 2. The first group has a total crate weight of 4 + 8 + 5 = 17. After adding the escort weight of 3, the truck load becomes 20. The second group has a total crate weight of 6 + 2 = 8. After adding the escort weight of 3, the truck load becomes 11. The heavier truck load for this split is 20. Therefore, the smallest possible value of the heaviest truck load is 16, achieved by splitting the crates into the groups 4, 8 and 5, 6, 2. --- #### Sample Input 2 ```text 6 3 2 3 10 1 1 1 1 10 ``` #### Sample Output 2 ```text 13 ```"