Let $ a = [a_1, a_2, \dots, a_n] $ be the initial array of diamond counts in the $ n $ cells.
Define the **adjacent sum vector** $ s = [s_1, s_2, \dots, s_{n-1}] $, where $ s_i = a_i + a_{i+1} $ for $ i = 1, 2, \dots, n-1 $.
Joe may perform up to $ m $ diamond-moving operations per minute for $ k $ minutes, for a total of at most $ m \cdot k $ operations.
Each operation is one of:
- Move a diamond from cell $ i $ to cell $ j $,
- Move a diamond from cell $ i $ to Joe’s pocket,
- Move a diamond from Joe’s pocket to cell $ j $.
Let $ b = [b_1, b_2, \dots, b_n] $ be the final configuration of diamonds in the cells after all operations.
**Constraints:**
- The adjacent sum vector must remain unchanged:
$$
b_i + b_{i+1} = a_i + a_{i+1} \quad \text{for all } i = 1, 2, \dots, n-1.
$$
- The total number of diamond moves (i.e., net transfers between cells and pocket) is at most $ m \cdot k $.
Let $ T = \sum_{i=1}^n a_i $ be the total diamonds initially.
Let $ T' = \sum_{i=1}^n b_i $ be the total diamonds remaining in the cells.
Then, the amount Joe steals is $ L = T - T' $.
We wish to **maximize** $ L = T - T' $, subject to:
1. $ b_i + b_{i+1} = a_i + a_{i+1} $ for all $ i = 1, \dots, n-1 $,
2. $ b_i \in \mathbb{Z}_{\geq 0} $ for all $ i $,
3. The total number of diamond movements required to transform $ a $ to $ b $ is at most $ m \cdot k $.
---
**Key Insight:**
The constraint $ b_i + b_{i+1} = a_i + a_{i+1} $ for all $ i $ implies that the **entire sequence $ b $** is determined by $ b_1 $, due to recurrence:
$$
b_2 = (a_1 + a_2) - b_1 \\
b_3 = (a_2 + a_3) - b_2 = (a_2 + a_3) - [(a_1 + a_2) - b_1] = b_1 + (a_3 - a_1) \\
b_4 = (a_3 + a_4) - b_3 = (a_3 + a_4) - [b_1 + a_3 - a_1] = (a_4 + a_1) - b_1 \\
\vdots
$$
In general, for all $ i $, $ b_i $ is an **affine function of $ b_1 $**:
$$
b_i = (-1)^{i+1} b_1 + c_i
$$
for some constants $ c_i $ determined by the original $ a $.
Thus, the set of all valid $ b $ is a **1-dimensional affine space** parameterized by $ b_1 $.
We require $ b_i \geq 0 $ for all $ i $, so $ b_1 $ must lie in an interval $ [L_{\min}, L_{\max}] $, defined by the non-negativity constraints on all $ b_i $.
Let $ b_1 = x $. Then $ b_i = (-1)^{i+1} x + c_i \geq 0 $ for all $ i $.
This gives linear inequalities in $ x $, defining a closed interval $ [x_{\min}, x_{\max}] $.
Then, the total diamonds remaining in the safe is:
$$
T' = \sum_{i=1}^n b_i = \sum_{i=1}^n \left[ (-1)^{i+1} x + c_i \right] = x \cdot \sum_{i=1}^n (-1)^{i+1} + \sum_{i=1}^n c_i
$$
Let $ S = \sum_{i=1}^n (-1)^{i+1} = \begin{cases}
1 & \text{if } n \text{ odd} \\
0 & \text{if } n \text{ even}
\end{cases} $
So:
- If $ n $ is even: $ T' = \sum c_i $ (constant), so $ L = T - T' $ is fixed → Joe cannot steal anything beyond what's forced.
- If $ n $ is odd: $ T' = x + C $, where $ C = \sum c_i $, so $ L = T - x - C $, and to **maximize** $ L $, we must **minimize** $ x $.
Thus:
> **Case 1: $ n $ even**
> The total diamonds in the safe is fixed under the adjacent-sum constraint. So Joe cannot steal any diamonds without triggering the alarm.
> $$
> \boxed{0}
> $$
> **Case 2: $ n $ odd**
> $ T' = x + C $, so $ L = T - x - C $.
> To maximize $ L $, minimize $ x $, subject to $ b_i = (-1)^{i+1} x + c_i \geq 0 $ for all $ i $.
> Let $ x_{\min} = \max_i \left( \frac{ -c_i }{ (-1)^{i+1} } \right) $ under the constraint $ b_i \geq 0 $.
> Then maximum stealable diamonds:
> $$
> L_{\max} = T - x_{\min} - C
> $$
But we are also constrained by the **number of moves**.
Let $ d_i = b_i - a_i $ be the net change in cell $ i $. The total number of diamond movements required is the **total variation** needed to go from $ a $ to $ b $, accounting for pocket transfers.
Each diamond moved from cell to cell counts as 1 move, from cell to pocket as 1, from pocket to cell as 1.
So the total number of moves is the **total amount of diamonds removed from cells minus those added to cells**, but since pocket acts as buffer, the total moves = total diamonds **taken out** (to pocket) + total diamonds **put in** (from pocket).
But note: net change in cell $ i $ is $ d_i = b_i - a_i $.
Let $ D^+ = \sum_{i: d_i > 0} d_i $ be total diamonds added to cells.
Let $ D^- = \sum_{i: d_i < 0} (-d_i) $ be total diamonds removed from cells.
Then total moves = $ D^+ + D^- $, since every diamond added required a move from pocket, every diamond removed required a move to pocket.
But note: $ D^+ = D^- + (T' - T) $? No.
Actually, total diamonds removed from cells = $ D^- $, total added = $ D^+ $, and net change: $ \sum d_i = T' - T = -L $.
But $ D^+ - D^- = T' - T = -L $
So $ D^+ = D^- - L $
Then total moves = $ D^+ + D^- = (D^- - L) + D^- = 2D^- - L $
Alternatively, since total diamonds removed from cells = $ D^- $, and those go to pocket, and total added to cells = $ D^+ $, from pocket, then total moves = $ D^- + D^+ = D^- + (D^- - L) = 2D^- - L $
But we can also express total moves as:
$$
\text{Total moves} = \sum_{i=1}^n |d_i| = \sum_{i=1}^n |b_i - a_i|
$$
This is because each unit change in a cell requires one move (whether in or out), and moves between cells are equivalent to two moves (out of one, into another), but the problem counts **each diamond transfer** as one move regardless of direction.
Wait: the problem says:
> One of the three following operations is regarded as moving a diamond:
> - moving a diamond from any cell to any other one,
> - moving a diamond from any cell to Joe's pocket,
> - moving a diamond from Joe's pocket to any cell.
So moving from cell $ i $ to cell $ j $ counts as **one** move.
Therefore, the total number of moves is **not** $ \sum |b_i - a_i| $, because if a diamond moves from cell $ i $ to cell $ j $, it reduces $ a_i $ by 1 and increases $ a_j $ by 1, so $ |d_i| + |d_j| = 2 $, but only **1 move** was made.
So we cannot use $ \sum |d_i| $.
We need to compute the **minimum number of moves** to transform $ a $ to $ b $, where moves can be:
- Cell → Cell (1 move, transfers 1 diamond),
- Cell → Pocket (1 move),
- Pocket → Cell (1 move).
This is equivalent to: we can transfer diamonds between any two cells at cost 1 per diamond, or to/from pocket at cost 1 per diamond.
This is a **transportation problem** with an extra "sink/source" (the pocket).
The minimum number of moves to go from $ a $ to $ b $ is:
$$
\min \left\{ \sum_{i \ne j} x_{ij} + \sum_i y_i + \sum_i z_i \right\}
$$
subject to:
- $ b_i = a_i - \sum_j x_{ji} + \sum_j x_{ij} - y_i + z_i $
- $ x_{ij} \geq 0 $, $ y_i \geq 0 $, $ z_i \geq 0 $
But this is complex.
**Better Insight:**
We are allowed to move diamonds arbitrarily between cells and pocket. The **minimum number of moves** to transform $ a $ to $ b $ is:
$$
\text{Moves} = \frac{1}{2} \sum_{i=1}^n |d_i| + \max(0, -\sum d_i)
$$
Wait — no.
Actually, the total net change is $ \sum d_i = T' - T = -L $. So Joe stole $ L $ diamonds.
The total "imbalance" that must be corrected via internal transfers is $ \sum_{d_i > 0} d_i = D^+ $, and $ \sum_{d_i < 0} (-d_i) = D^- $, and $ D^+ - D^- = T' - T = -L $, so $ D^+ = D^- - L $.
The **minimum number of moves** is:
- $ D^- $ diamonds removed from cells → to pocket: $ D^- $ moves.
- $ D^+ $ diamonds added to cells ← from pocket: $ D^+ $ moves.
- But we can also move diamonds **between cells** to reduce moves.
Each diamond moved from a cell with surplus to one with deficit reduces both $ D^- $ and $ D^+ $ by 1, and costs only 1 move instead of 2.
So optimal strategy: move as many diamonds as possible **between cells**.
The maximum number of diamonds that can be moved between cells is $ \min(D^-, D^+) $.
Then:
- Internal moves: $ \min(D^-, D^+) $
- Pocket moves: $ D^- - \min(D^-, D^+) + D^+ - \min(D^-, D^+) = |D^- - D^+| = L $
So total moves:
$$
\text{Moves} = \min(D^-, D^+) + L
$$
But since $ D^+ = D^- - L $, then $ \min(D^-, D^+) = D^+ = D^- - L $
So:
$$
\text{Moves} = (D^- - L) + L = D^-
$$
Wait — that can’t be right.
Let’s take an example:
Initial: [2, 0], target: [1, 1]. Then $ d = [-1, +1] $, $ D^- = 1, D^+ = 1, L = 0 $
Move 1 diamond from cell 1 to cell 2: 1 move. Total moves = 1.
$ D^- = 1 $, so moves = $ D^- = 1 $ — matches.
Another: Initial [3, 0], target [1, 1]. Then $ d = [-2, +1] $, $ D^- = 2, D^+ = 1, L = 1 $
We can move 1 diamond from cell 1 to cell 2 (1 move), and move 1 diamond from cell 1 to pocket (1 move). Total moves = 2.
$ D^- = 2 $, so moves = $ D^- = 2 $ — matches.
Another: Initial [0, 0], target [1, 1]. $ d = [1,1] $, $ D^- = 0, D^+ = 2, L = -2 $? No, $ T' = 2, T = 0, L = -2 $? But Joe can't steal negative.
Wait: $ L = T - T' = 0 - 2 = -2 $, meaning Joe put in 2 diamonds — not stealing.
But we are maximizing stealing, so we consider $ L \geq 0 $.
In our case, $ T' \leq T $, so $ L \geq 0 $.
So in general:
Let $ D^- = \sum_{d_i < 0} (-d_i) $ = total diamonds removed from cells.
Let $ D^+ = \sum_{d_i > 0} d_i $ = total diamonds added to cells.
Then $ D^- - D^+ = T - T' = L $
So $ D^- = D^+ + L $
Total moves = $ D^- $ (because we can use internal transfers to cover $ D^+ $ diamonds, and the remaining $ L $ must go to pocket, so total moves = $ D^- $)
Why? Because:
- We can transfer up to $ D^+ $ diamonds from cells with deficit to cells with surplus? No — we need to remove $ D^- $ diamonds from cells, and add $ D^+ $ to others.
Actually, the minimum number of moves is $ D^- $, because:
- Every diamond that ends up **outside** the cells (in Joe’s pocket) must have been moved out at least once.
- Every diamond that is moved from one cell to another reduces the need to move to/from pocket.
- But since we are only allowed to move diamonds that are **in cells** to other places, the **total number of times a diamond leaves a cell** is exactly $ D^- $, and each such exit is one move.
- Diamonds can be moved between cells, but each such move still requires one "exit" from a cell and one "entry" to another — but the entry doesn't count as a move if we're counting only operations (and each operation is one transfer).
Wait — the problem counts **each transfer** as one move, regardless of direction.
So if a diamond moves from cell A to cell B, that’s **one move**.
If a diamond moves from cell A to pocket, that’s **one move**.
So to go from $ a $ to $ b $, we need to account for:
- The net outflow from each cell: $ a_i - b_i $ if positive = diamonds removed from cell $ i $.
- The net inflow: $ b_i - a_i $ if positive = diamonds added to cell $ i $.
The total number of moves is the **minimum number of transfers** needed to achieve the net change.
This is a classic problem: the minimum number of moves to transform one distribution to another with transfers between any two positions and an external sink/source.
The answer is:
> The minimum number of moves is equal to the **total outflow** from the cells, which is $ \sum_{i=1}^n \max(0, a_i - b_i) = D^- $
Because:
- Every diamond that leaves a cell must be moved out in one operation.
- Once it’s out, it can be moved to another cell (1 move) or to pocket (1 move).
- But if it goes to another cell, it is then "inflow" to that cell, which doesn't require an additional move beyond the initial outflow.
So total moves = total diamonds removed from cells = $ \sum_{i=1}^n \max(0, a_i - b_i) = D^- $
And since $ D^- = D^+ + L $, and $ D^+ \geq 0 $, we have $ D^- \geq L $
So constraint: $ D^- \leq m \cdot k $
But $ D^- = \sum_{i=1}^n \max(0, a_i - b_i) $
And we want to **maximize** $ L = T - T' = T - \sum b_i $
Subject to:
- $ b_i + b_{i+1} = a_i + a_{i+1} $ for all $ i $
- $ b_i \geq 0 $
- $ \sum_{i=1}^n \max(0, a_i - b_i) \leq m \cdot k $
And as established, if $ n $ is even, $ T' $ is fixed → $ L = 0 $
If $ n $ is odd, then $ b_i = (-1)^{i+1} x + c_i $, and $ T' = x + C $, so $ L = T - x - C $
We want to **minimize $ x $** to maximize $ L $, but subject to:
1. $ b_i = (-1)^{i+1} x + c_i \geq 0 $ → gives lower bound $ x \geq x_{\min} $
2. $ \sum_{i=1}^n \max(0, a_i - b_i) \leq m \cdot k $
Let $ f(x) = \sum_{i=1}^n \max(0, a_i - b_i(x)) $
We want the **smallest** $ x \geq x_{\min} $ such that $ f(x) \leq m \cdot k $, then $ L = T - x - C $
But $ f(x) $ is a **piecewise linear, non-increasing** function of $ x $, because as $ x $ increases, $ b_i(x) $ increases for odd $ i $, decreases for even $ i $, so $ a_i - b_i(x) $ decreases for odd $ i $, increases for even $ i $.
Wait: $ b_i(x) = (-1)^{i+1} x + c_i $
So for $ i $ odd: $ b_i = x + c_i $ → increases with $ x $
For $ i $ even: $ b_i = -x + c_i $ → decreases with $ x $
So $ a_i - b_i $:
- For odd $ i $: $ a_i - x - c_i $ → decreases as $ x $ increases
- For even $ i $: $ a_i + x - c_i $ → increases as $ x $ increases
So $ \max(0, a_i - b_i) $:
- For odd $ i $: decreases with $ x $
- For even $ i $: increases with $ x $
Thus $ f(x) = \sum \max(0, a_i - b_i(x)) $ is **not monotonic** — it may have a minimum.
But we are trying to **minimize $ x $** to maximize $ L $, so we want the **smallest** $ x \geq x_{\min} $ such that $ f(x) \leq m \cdot k $
We can binary search on $ x $ over the feasible interval $ [x_{\min}, x_{\max}] $, compute $ f(x) $, and find the minimal $ x $ satisfying the constraint.
Then $ L = T - x - C $
**Final Answer:**
- If $ n $ is even → $ \boxed{0} $
- If $ n $ is odd:
- Compute $ c_i $ from recurrence: $ b_1 = x $, $ b_2 = (a_1 + a_2) - x $, $ b_3 = (a_2 + a_3) - b_2 = a_3 - a_1 + x $, etc.
- Determine $ x_{\min} = \max_i \left( \frac{ -c_i }{ (-1)^{i+1} } \right) $ such that $ b_i \geq 0 $
- Let $ T' = x + C $, where $ C = \sum c_i $
- Define $ f(x) = \sum_{i=1}^n \max(0, a_i - b_i(x)) $
- Find the minimal $ x \in [x_{\min}, x_{\max}] $ such that $ f(x) \leq m \cdot k $
- Then answer = $ T - x - C $
But since $ m, k \leq 10^9 $, and $ n \leq 10^4 $, we can binary search on $ x $ over a bounded interval.
The values of $ c_i $ are linear combinations of $ a_j $, which are $ \leq 10^5 $, so $ x $ is bounded by $ O(n \cdot \max a_i) \leq 10^9 $, which is acceptable for binary search.
Thus, the algorithm is:
1. If $ n $ even: return 0
2. Else:
- Compute $ c_1 = 0 $, $ c_2 = a_1 + a_2 $, $ c_3 = a_3 - a_1 $, $ c_4 = a_4 + a_1 $, $ c_5 = a_5 - a_1 $, etc.
General:
$ c_1 = 0 $
$ c_i = a_{i-1} + a_i - c_{i-1} $ for $ i \geq 2 $
Actually, from recurrence:
$ b_i = (-1)^{i+1} x + c_i $
$ b_1 = x = 1 \cdot x + 0 \Rightarrow c_1 = 0 $
$ b_2 = (a_1 + a_2) - b_1 = (a_1 + a_2) - x = -x + (a_1 + a_2) \Rightarrow c_2 = a_1 + a_2 $
$ b_3 = (a_2 + a_3) - b_2 = (a_2 + a_3) - [(a_1 + a_2) - x] = x + (a_3 - a_1) \Rightarrow c_3 = a_3 - a_1 $
$ b_4 = (a_3 + a_4) - b_3 = (a_3 + a_4) - [x + a_3 - a_1] = -x + (a_4 + a_1) \Rightarrow c_4 = a_4 + a_1 $
So recurrence:
$ c_1 = 0 $
$ c_i = a_{i-1} + a_i - c_{i-1} $ for $ i \geq 2 $
But note: $ b_i + b_{i+1} = a_i + a_{i+1} $, so $ b_{i+1} = a_i + a_{i+1} - b_i $
So $ c_{i+1} = a_i + a_{i+1} - c_i $, and the sign alternates.
- Compute $ C = \sum_{i=1}^n c_i $
- Compute $ x_{\min} = \max_{i=1}^n \left( \frac{ -c_i }{ (-1)^{i+1} } \right) $ under the constraint $ b_i \geq 0 $
i.e., for each $ i $:
if $ i $ odd: $ x + c_i \geq 0 \Rightarrow x \geq -c_i $
if $ i $ even: $ -x + c_i \geq 0 \Rightarrow x \leq c_i $
So $ x \geq \max_{i \text{ odd}} (-c_i) $, and $ x \leq \min_{i \text{ even}} (c_i) $
So $ x_{\min} = \max_{i \text{ odd}} (-c_i) $, $ x_{\max} = \min_{i \text{ even}} (c_i) $
- If $ x_{\min} > x_{\max} $, no solution → but problem guarantees at least one check, so assume feasible.
- Define $ f(x) = \sum_{i=1}^n \max(0, a_i - b_i(x)) = \sum_{i=1}^n \max(0, a_i - [ (-1)^{i+1} x + c_i ]) $
- Binary search on $ x \in [x_{\min}, x_{\max}] $ for the **smallest** $ x $ such that $ f(x) \leq m \cdot k $
- Answer: $ T - x - C $
Note: Since $ f(x) $ is piecewise linear and convex? Not necessarily, but we can evaluate it in $ O(n) $ per evaluation, and binary search over $ O(\text{range}) $, but range is up to $ 10^9 $, so $ \log(10^9) \approx 30 $ iterations, each $ O(n) $, total $ O(n \log \text{range}) \approx 10^4 \cdot 30 = 3 \cdot 10^5 $, acceptable.
**Final Output:**
$$
\boxed{
\begin{cases}
0 & \text{if } n \text{ is even} \\
T - x^* - C & \text{if } n \text{ is odd}
\end{cases}
}
$$
where $ x^* $ is the minimal $ x \in [x_{\min}, x_{\max}] $ such that $ \sum_{i=1}^n \max(0, a_i - b_i(x)) \leq m \cdot k $, with $ b_i(x) = (-1)^{i+1} x + c_i $, $ c_i $ defined recursively by $ c_1 = 0 $, $ c_i = a_{i-1} + a_i - c_{i-1} $ for $ i \geq 2 $, $ C = \sum c_i $, $ T = \sum a_i $.