Let $ a = (a_1, a_2, \dots, a_n) $ be the initial vector 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} $.
Joe may perform up to $ m $ diamond-moving operations per minute for $ k $ minutes, for a total of at most $ mk $ 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 $ i $.
Let $ b = (b_1, b_2, \dots, b_n) $ be the final configuration after all operations.
**Constraint:** 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.
$$
Let $ T $ be the total number of diamonds Joe steals:
$$
T = \sum_{i=1}^n a_i - \sum_{i=1}^n b_i.
$$
**Objective:** Maximize $ T $, subject to:
- $ b_i + b_{i+1} = a_i + a_{i+1} $ for all $ i \in \{1, \dots, n-1\} $,
- $ b_i \in \mathbb{Z}_{\geq 0} $ for all $ i $,
- The total number of diamond movements (i.e., net changes in cell contents, counting both additions and removals) is at most $ mk $.
---
### Key Insight:
The constraint $ b_i + b_{i+1} = a_i + a_{i+1} $ for all $ i $ implies that the vector $ b $ is **completely determined** by $ b_1 $, via 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, \\
\text{and so on.}
$$
In general, for all $ i $, $ b_i $ is an affine function of $ b_1 $:
$$
b_i =
\begin{cases}
b_1 + c_i & \text{if } i \text{ odd}, \\
d_i - b_1 & \text{if } i \text{ even},
\end{cases}
$$
where $ c_i, d_i $ are constants derived from the initial $ a_j $'s.
Thus, the entire vector $ b $ is parameterized by a single variable $ x = b_1 \in \mathbb{Z}_{\geq 0} $, and the rest are determined.
Moreover, all $ b_i \geq 0 $, so $ x $ must lie in a closed interval $ [L, U] \subset \mathbb{Z} $, defined by the non-negativity constraints on all $ b_i $.
Let $ S = \sum_{i=1}^n a_i $, and $ B(x) = \sum_{i=1}^n b_i(x) $. Then the stolen amount is:
$$
T(x) = S - B(x)
$$
We wish to **maximize** $ T(x) $, i.e., **minimize** $ B(x) $, over $ x \in [L, U] \cap \mathbb{Z} $.
But we are also constrained by the **total number of operations** needed to transform $ a $ into $ b(x) $.
Let $ d_i = |b_i - a_i| $. The total number of operations required is **not** $ \sum |b_i - a_i| $, because:
- Moving a diamond from cell $ i $ to cell $ j $ counts as **one** operation, and reduces both $ a_i $ and increases $ a_j $.
- So the **minimum number of operations** needed to transform $ a $ to $ b $ is equal to the **total net outflow** from all cells, which is:
$$
\text{Operations}(a \to b) = \sum_{i: b_i < a_i} (a_i - b_i) = \sum_{i: b_i > a_i} (b_i - a_i)
$$
Because every diamond moved out of a cell must be moved into another or into Joe’s pocket, and vice versa.
Thus, the number of operations required is exactly the **total amount of diamonds removed from cells** (i.e., the sum of decreases), which equals the **total amount stolen plus the total amount moved between cells**.
But since diamonds moved between cells do not contribute to Joe’s loot, to **maximize loot**, we want to **minimize** the number of diamonds moved between cells, and **maximize** the number moved directly to Joe’s pocket.
In fact, the **minimum number of operations** required to achieve configuration $ b $ from $ a $ is:
$$
\text{Ops}(a \to b) = \sum_{i=1}^n \max(0, a_i - b_i)
$$
Why? Because:
- Every diamond that is **removed** from a cell (i.e., $ a_i - b_i > 0 $) must be moved either to another cell or to Joe’s pocket.
- But if we are allowed to move diamonds **directly to Joe’s pocket**, then we can avoid moving diamonds between cells entirely — we can just remove $ a_i - b_i $ diamonds from cell $ i $ and put them in Joe’s pocket, in $ a_i - b_i $ operations.
- Conversely, if $ b_i > a_i $, we must add $ b_i - a_i $ diamonds to cell $ i $, which must come from Joe’s pocket, costing $ b_i - a_i $ operations.
So total operations:
$$
\text{Ops}(a \to b) = \sum_{i=1}^n |a_i - b_i| / 2? \quad \text{No!}
$$
Wait — correction:
Each operation moves **one diamond**. If we move a diamond from cell $ i $ to cell $ j $, that’s one operation, and it reduces $ a_i $ by 1 and increases $ a_j $ by 1.
If we move from cell $ i $ to pocket, it reduces $ a_i $ by 1, increases pocket by 1.
So the **total number of operations** needed to reach $ b $ from $ a $ is:
$$
\sum_{i=1}^n \max(0, a_i - b_i) + \sum_{i=1}^n \max(0, b_i - a_i) = \sum_{i=1}^n |a_i - b_i|
$$
Wait — **no!** That would be true if each change required an independent operation, but moving a diamond from cell $ i $ to cell $ j $ changes both $ a_i $ and $ a_j $ in one operation.
So the **minimum number of operations** is **not** $ \sum |a_i - b_i| $, but rather:
Let $ D^+ = \sum_{i: b_i > a_i} (b_i - a_i) $ — total diamonds to be added to cells
Let $ D^- = \sum_{i: b_i < a_i} (a_i - b_i) $ — total diamonds to be removed from cells
Then, we can move up to $ \min(D^+, D^-) $ diamonds from overfilled cells to underfilled cells, each such move counts as 1 operation and reduces both $ D^+ $ and $ D^- $ by 1.
The remaining diamonds must be moved to/from Joe’s pocket:
- $ D^- - \min(D^+, D^-) = \max(0, D^- - D^+) $ diamonds are stolen (put in pocket)
- $ D^+ - \min(D^+, D^-) = \max(0, D^+ - D^-) $ diamonds are added from pocket
But Joe’s **loot** is exactly the amount stolen: $ T = D^- - \min(D^+, D^-) $
And the total number of operations is:
$$
\min(D^+, D^-) + (D^- - \min(D^+, D^-)) + (D^+ - \min(D^+, D^-)) = D^+ + D^-
$$
Wait — that’s just $ \sum |a_i - b_i| $
But that can’t be: if we move a diamond from cell 1 to cell 2, we reduce $ |a_1 - b_1| $ by 1 and $ |a_2 - b_2| $ by 1, but only use 1 operation.
So the total number of operations is **not** $ \sum |a_i - b_i| $, but rather:
Let $ \Delta_i = b_i - a_i $
Then total operations = $ \sum_{i: \Delta_i > 0} \Delta_i + \sum_{i: \Delta_i < 0} (-\Delta_i) - \text{saved by internal transfers} $
Actually, the **minimum number of operations** to transform $ a $ to $ b $ is:
$$
\text{Ops}(a \to b) = \sum_{i=1}^n \max(0, a_i - b_i)
$$
**Why?** Because:
- Every diamond that is removed from a cell must be moved in an operation (either to another cell or to pocket).
- Every diamond added to a cell must come from an operation (from pocket or another cell).
- But if we move a diamond from a cell with excess to a cell with deficit, that one operation satisfies both a removal and an addition.
So the **minimum number of operations** is the **total amount of diamonds that must leave the system** (i.e., go to Joe’s pocket) **plus** the total amount of diamonds that are moved between cells.
But since we can move diamonds between cells freely, the **minimum number of operations** required is:
$$
\text{Ops}(a \to b) = \sum_{i=1}^n \max(0, a_i - b_i)
$$
**Proof sketch:**
- We can always move diamonds directly from overfilled cells to Joe’s pocket: that takes $ \sum \max(0, a_i - b_i) $ operations.
- We can also move diamonds from overfilled to underfilled cells, but that doesn’t reduce the number of operations below the total outflow — because every diamond that leaves a cell must be moved in an operation, regardless of destination.
- The key is: **each operation removes exactly one diamond from a cell** (if going to pocket or another cell), and **adds one diamond to a cell** (if coming from pocket or another cell).
- So the number of operations is equal to the total number of diamonds removed from cells, which is $ \sum \max(0, a_i - b_i) $, **because** every diamond that ends up in Joe’s pocket was removed from a cell, and every diamond that moves between cells was removed from one cell and added to another — so the number of removals equals the number of additions, and each operation accounts for one removal.
Thus, **minimum operations** to reach configuration $ b $ is:
$$
\text{Ops}(a \to b) = \sum_{i=1}^n \max(0, a_i - b_i)
$$
And Joe’s loot is:
$$
T = \sum_{i=1}^n a_i - \sum_{i=1}^n b_i = \sum_{i=1}^n (a_i - b_i) = \sum_{i=1}^n \max(0, a_i - b_i) - \sum_{i=1}^n \max(0, b_i - a_i)
$$
But since $ \sum (a_i - b_i) = T $, and $ \sum \max(0, a_i - b_i) - \sum \max(0, b_i - a_i) = T $, we have:
Let $ R = \sum \max(0, a_i - b_i) $, $ A = \sum \max(0, b_i - a_i) $, then $ T = R - A $, and $ \text{Ops} = R $.
But also, since $ \sum (a_i - b_i) = T $, and $ R - A = T $, then $ A = R - T $, so $ \text{Ops} = R = T + A \geq T $.
But we can choose $ b $ to minimize $ \text{Ops} $ for a given $ T $, or maximize $ T $ for a given $ \text{Ops} \leq mk $.
We want to **maximize $ T $** subject to $ \text{Ops}(a \to b) \leq mk $, and $ b $ satisfying the adjacent sum constraints.
But from above, $ \text{Ops}(a \to b) = \sum \max(0, a_i - b_i) $, and $ T = \sum (a_i - b_i) $.
So $ T = \sum (a_i - b_i) = \sum \max(0, a_i - b_i) - \sum \max(0, b_i - a_i) = \text{Ops} - A \leq \text{Ops} $
Thus, $ T \leq \text{Ops} \leq mk $, so **maximum possible loot is at most $ mk $**.
But we are constrained by the adjacent sum invariants.
So the problem reduces to:
> Among all vectors $ b \in \mathbb{Z}_{\geq 0}^n $ such that $ b_i + b_{i+1} = a_i + a_{i+1} $ for all $ i $, maximize $ T = \sum (a_i - b_i) $, subject to $ \sum \max(0, a_i - b_i) \leq mk $.
But since $ T = \sum (a_i - b_i) $, and $ b_i $ is determined by $ b_1 = x $, we can express $ T $ as a linear function of $ x $, and $ \sum \max(0, a_i - b_i(x)) $ as a piecewise linear convex function of $ x $.
So:
### Final Formalization:
Let $ a = (a_1, \dots, a_n) \in \mathbb{Z}_{\geq 0}^n $ be given.
Define the sequence $ b(x) = (b_1(x), \dots, b_n(x)) $, where $ b_1(x) = x $, and for $ i \geq 2 $:
$$
b_i(x) =
\begin{cases}
x + c_i & \text{if } i \text{ odd}, \\
d_i - x & \text{if } i \text{ even},
\end{cases}
$$
where $ c_i, d_i $ are constants derived from $ a $, such that $ b_i(x) + b_{i+1}(x) = a_i + a_{i+1} $.
Let $ L = \max_{i} \left( \max(0, \lceil -c_i \rceil) \text{ if } i \text{ odd}, \lceil d_i \rceil \text{ if } i \text{ even} \right) $ — wait, better:
Constraints: $ b_i(x) \geq 0 $ for all $ i $.
So:
- For odd $ i $: $ x + c_i \geq 0 \Rightarrow x \geq -c_i $
- For even $ i $: $ d_i - x \geq 0 \Rightarrow x \leq d_i $
Thus, $ x \in [L, U] $, where:
$$
L = \max_{i \text{ odd}} (-c_i), \quad U = \min_{i \text{ even}} d_i
$$
Let $ T(x) = \sum_{i=1}^n (a_i - b_i(x)) $
This is linear in $ x $: $ T(x) = C - D \cdot x $, for some constants $ C, D $ (depending on parity of $ n $).
We want to **maximize** $ T(x) $, i.e., **minimize** $ x $, over $ x \in [L, U] \cap \mathbb{Z} $, **subject to**:
$$
\sum_{i=1}^n \max(0, a_i - b_i(x)) \leq mk
$$
Let $ R(x) = \sum_{i=1}^n \max(0, a_i - b_i(x)) $
We want:
$$
\max_{x \in [L, U] \cap \mathbb{Z}} T(x) \quad \text{subject to} \quad R(x) \leq mk
$$
Since $ T(x) $ is linear and decreasing in $ x $, and $ R(x) $ is piecewise linear and convex (as sum of max-of-linear functions), the feasible set is an interval of integers, and the maximum $ T(x) $ occurs at the **smallest feasible** $ x $.
Thus, the solution is:
> Find the smallest integer $ x \in [L, U] $ such that $ R(x) \leq mk $, then output $ T(x) = \sum (a_i - b_i(x)) $.
If no such $ x $ exists, output 0 (though problem guarantees at least one valid configuration).
---
### Final Answer (Formal Statement):
Let $ a \in \mathbb{Z}_{\geq 0}^n $, $ m, k \in \mathbb{Z}_{>0} $.
Define $ b_1 = x \in \mathbb{Z} $, and recursively define $ b_i $ for $ i = 2 $ to $ n $ via:
$$
b_i = (a_{i-1} + a_i) - b_{i-1}
$$
Let $ L = \max_{i \in \{1,\dots,n\}} \left( \max_{\substack{j \leq i \\ j \text{ odd}}} \left( -\left( \sum_{\ell=1}^{j-1} (-1)^{\ell} (a_\ell + a_{\ell+1}) \right) \right), \quad \min_{\substack{j \leq n \\ j \text{ even}}} \left( \sum_{\ell=1}^{j-1} (-1)^{\ell} (a_\ell + a_{\ell+1}) \right) \right) $ — too messy.
Better: Compute $ b_i(x) $ explicitly as:
Let $ s_i = a_i + a_{i+1} $ for $ i=1,\dots,n-1 $
Then:
- $ b_1 = x $
- $ b_2 = s_1 - x $
- $ b_3 = s_2 - b_2 = s_2 - s_1 + x $
- $ b_4 = s_3 - b_3 = s_3 - s_2 + s_1 - x $
- $ b_5 = s_4 - b_4 = s_4 - s_3 + s_2 - s_1 + x $
So:
$$
b_i(x) =
\begin{cases}
x + \sum_{j=1}^{i-1} (-1)^{j+1} s_j & \text{if } i \text{ odd}, \\
\sum_{j=1}^{i-1} (-1)^j s_j - x & \text{if } i \text{ even}.
\end{cases}
$$
Define $ c_i = \sum_{j=1}^{i-1} (-1)^{j+1} s_j $ for odd $ i $,
and $ d_i = \sum_{j=1}^{i-1} (-1)^j s_j $ for even $ i $
Then:
- $ b_i(x) = x + c_i $ for odd $ i $
- $ b_i(x) = d_i - x $ for even $ i $
Then non-negativity constraints:
- For odd $ i $: $ x \geq -c_i $
- For even $ i $: $ x \leq d_i $
So $ L = \max_{i \text{ odd}} (-c_i) $, $ U = \min_{i \text{ even}} d_i $
Let $ T(x) = \sum_{i=1}^n (a_i - b_i(x)) $
Let $ R(x) = \sum_{i=1}^n \max(0, a_i - b_i(x)) $
Find $ x^* = \min \{ x \in \mathbb{Z} \cap [L, U] \mid R(x) \leq mk \} $
Then output $ T(x^*) $
If no such $ x $, output 0.
But since $ T(x) $ is linear and decreasing in $ x $, and $ R(x) $ is convex and piecewise linear, we can binary search on $ x \in [L, U] $ to find the minimal $ x $ such that $ R(x) \leq mk $, then compute $ T(x) $.
---
### Final Answer (as required):
$$
\boxed{
\begin{aligned}
&\text{Let } s_i = a_i + a_{i+1} \text{ for } i = 1, \dots, n-1. \\
&\text{Define } c_i = \sum_{j=1}^{i-1} (-1)^{j+1} s_j \text{ for odd } i, \quad d_i = \sum_{j=1}^{i-1} (-1)^j s_j \text{ for even } i. \\
&\text{Let } L = \max_{\substack{i=1,\dots,n \\ i \text{ odd}}} (-c_i), \quad U = \min_{\substack{i=1,\dots,n \\ i \text{ even}}} d_i. \\
&\text{Define } b_i(x) =
\begin{cases}
x + c_i & \text{if } i \text{ odd}, \\
d_i - x & \text{if } i \text{ even}.
\end{cases} \\
&\text{Let } T(x) = \sum_{i=1}^n (a_i - b_i(x)), \quad R(x) = \sum_{i=1}^n \max(0, a_i - b_i(x)). \\
&\text{Find } x^* = \min \{ x \in \mathbb{Z} \cap [L, U] \mid R(x) \leq mk \}. \\
&\text{Output } T(x^*).
\end{aligned}
}
$$