3449. Maximize the Minimum Game Score Hard

1/**
2 * [3449] Maximize the Minimum Game Score
3 *
4 * You are given an array points of size n and an integer m. There is another array gameScore of size n, where gameScore[i] represents the score achieved at the i^th game. Initially, gameScore[i] == 0 for all i.
5 * You start at index -1, which is outside the array (before the first position at index 0). You can make at most m moves. In each move, you can either:
6 * 
7 * 	Increase the index by 1 and add points[i] to gameScore[i].
8 * 	Decrease the index by 1 and add points[i] to gameScore[i].
9 * 
10 * Note that the index must always remain within the bounds of the array after the first move.
11 * Return the maximum possible minimum value in gameScore after at most m moves.
12 *  
13 * <strong class="example">Example 1:
14 * <div class="example-block">
15 * Input: <span class="example-io">points = [2,4], m = 3</span>
16 * Output: <span class="example-io">4</span>
17 * Explanation:
18 * Initially, index i = -1 and gameScore = [0, 0].
19 * <table style="border: 1px solid black;">
20 * 	<thead>
21 * 		<tr>
22 * 			<th style="border: 1px solid black;">Move</th>
23 * 			<th style="border: 1px solid black;">Index</th>
24 * 			<th style="border: 1px solid black;">gameScore</th>
25 * 		</tr>
26 * 	</thead>
27 * 	<tbody>
28 * 		<tr>
29 * 			<td style="border: 1px solid black;">Increase i</td>
30 * 			<td style="border: 1px solid black;">0</td>
31 * 			<td style="border: 1px solid black;">[2, 0]</td>
32 * 		</tr>
33 * 		<tr>
34 * 			<td style="border: 1px solid black;">Increase i</td>
35 * 			<td style="border: 1px solid black;">1</td>
36 * 			<td style="border: 1px solid black;">[2, 4]</td>
37 * 		</tr>
38 * 		<tr>
39 * 			<td style="border: 1px solid black;">Decrease i</td>
40 * 			<td style="border: 1px solid black;">0</td>
41 * 			<td style="border: 1px solid black;">[4, 4]</td>
42 * 		</tr>
43 * 	</tbody>
44 * </table>
45 * The minimum value in gameScore is 4, and this is the maximum possible minimum among all configurations. Hence, 4 is the output.
46 * </div>
47 * <strong class="example">Example 2:
48 * <div class="example-block">
49 * Input: <span class="example-io">points = [1,2,3], m = 5</span>
50 * Output: <span class="example-io">2</span>
51 * Explanation:
52 * Initially, index i = -1 and gameScore = [0, 0, 0].
53 * <table style="border: 1px solid black;">
54 * 	<thead>
55 * 		<tr>
56 * 			<th style="border: 1px solid black;">Move</th>
57 * 			<th style="border: 1px solid black;">Index</th>
58 * 			<th style="border: 1px solid black;">gameScore</th>
59 * 		</tr>
60 * 	</thead>
61 * 	<tbody>
62 * 		<tr>
63 * 			<td style="border: 1px solid black;">Increase i</td>
64 * 			<td style="border: 1px solid black;">0</td>
65 * 			<td style="border: 1px solid black;">[1, 0, 0]</td>
66 * 		</tr>
67 * 		<tr>
68 * 			<td style="border: 1px solid black;">Increase i</td>
69 * 			<td style="border: 1px solid black;">1</td>
70 * 			<td style="border: 1px solid black;">[1, 2, 0]</td>
71 * 		</tr>
72 * 		<tr>
73 * 			<td style="border: 1px solid black;">Decrease i</td>
74 * 			<td style="border: 1px solid black;">0</td>
75 * 			<td style="border: 1px solid black;">[2, 2, 0]</td>
76 * 		</tr>
77 * 		<tr>
78 * 			<td style="border: 1px solid black;">Increase i</td>
79 * 			<td style="border: 1px solid black;">1</td>
80 * 			<td style="border: 1px solid black;">[2, 4, 0]</td>
81 * 		</tr>
82 * 		<tr>
83 * 			<td style="border: 1px solid black;">Increase i</td>
84 * 			<td style="border: 1px solid black;">2</td>
85 * 			<td style="border: 1px solid black;">[2, 4, 3]</td>
86 * 		</tr>
87 * 	</tbody>
88 * </table>
89 * The minimum value in gameScore is 2, and this is the maximum possible minimum among all configurations. Hence, 2 is the output.
90 * </div>
91 *  
92 * Constraints:
93 * 
94 * 	2 <= n == points.length <= 5 * 10^4
95 * 	1 <= points[i] <= 10^6
96 * 	1 <= m <= 10^9
97 * 
98 */
99pub struct Solution {}
100
101// problem: https://leetcode.com/problems/maximize-the-minimum-game-score/
102// discuss: https://leetcode.com/problems/maximize-the-minimum-game-score/discuss/?currentPage=1&orderBy=most_votes&query=
103
104// submission codes start here
105
106impl Solution {
107    pub fn max_score(points: Vec<i32>, m: i32) -> i64 {
108        
109    }
110}
111
112// submission codes end
113
114#[cfg(test)]
115mod tests {
116    use super::*;
117
118    #[test]
119    fn test_3449() {
120    }
121}
122