{"problem":{"name":"C. Forklifter","description":{"content":"After the completion of his manga Tights in The Wind, mangaka Kakushi Gotou took a part time job as a JUMP! comics warehouse forklifter. The warehouse is a parallelogram with row length $r$ and colum","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10268C"},"statements":[{"statement_type":"Markdown","content":"After the completion of his manga Tights in The Wind, mangaka Kakushi Gotou took a part time job as a JUMP! comics warehouse forklifter.\n\nThe warehouse is a parallelogram with row length $r$ and column length $c$. The storage slots of the warehouse are mini hexagons denoted by coordinates $(i, j)$, where $i$ is its row number and $j$ is its column number. The slot at coordinate $(i, j)$ has $A_{(i , j})$ JUMP! comics already stacked on it.\n\nWe define the instability of the warehouse stacks to be the largest difference in height between any two adjacent storage slots in the warehouse. We say two stacks are adjacent if their hexagonal slots share a side. More formally, the slot at coordinate $(i, j)$ is adjacent to the slots at coordinates $(i, j -1)$, $(i, j + 1)$, $(i -1, j)$, $(i -1, j + 1)$, $(i + 1, j -1)$, and $(i + 1, j)$ (if they exist). The arrows in the above grid visually depict adjacent nodes.\n\nKakushi's job is to minimize this instability in order to prevent a potential book avalanche. To do so, he can bring in up to $k$ JUMP! comics, which he can pile up on any stack he wishes. To avoid garnering hatred from his forklifter senpais, Kakushi does not want to move comics initially/already stacked in the warehouse.\n\nWhat is the minimum instability of the warehouse if Kakushi brings in the optimal number of JUMP! comics and places them on the stacks optimally?\n\n*Note: The warehouse grid is NOT a rectangle, it is a slanted parallelogram. Look at the sample input/output explanation or the above warehouse grid example for clarity.*\n\nThe first line of input contains $t$, the number of test cases. \n\nEach test case begins with three integers $r$, $c$, and $k$, the number of rows of the warehouse, the number of columns of the warehouse, and the maximum number of comics Kakushi can bring in, respectively.\n\n$r$ lines then follow, each containing $c$ integers. The $j$th integer in the $i$th line denotes the number of comics at coordinate $(i, j)$, i.e. $A_{(i , j})$.\n\nOutput one integer, the minimum instability obtainable by placing up to $k$ JUMP! comics in the warehouse stacks.\n\n*For all subtasks*\n\n$1 <= A_{(i , j}) <= 10^(12)$\n\n$0 <= k <= 10^(18)$\n\n$1 <= r, c, r c <= 10^5$\n\nThe sum of the $r c$'s in a single file is $<= 4 dot.op 10^5$\n\n$1 <= t <= 10$\n\n$r c > 1$\n\n*Subtask 1* (5 points):\n\n$k = 0$\n\n*Subtask 2* (10 points):\n\n$r, c, r c, k <= 200$\n\n*Subtask 3* (15 points):\n\n$r, c, r c <= 200$\n\n*Subtask 4* (15 points):\n\n$r, c, r c <= 3000$\n\n*Subtask 5* (20 points):\n\n$r = 1$ or $c = 1$\n\n*Subtask 6* (20 points):\n\n$r c <= 30000$\n\nThe sum of the $r c$'s in a single file is $<= 60000$\n\n*Subtask 7* (15 points):\n\nNo additional constraints.\n\n_Note:_ The sample case is not valid for the first and fifth subtasks. It is valid for the other subtasks.\n\nThe warehouse has $r = 3$ rows and $c = 5$ columns. Kakushi can bring in up to $k = 12$ JUMP! comics. The warehouse initially looks like the following:\n\nKakushi can choose to bring in $11$ comics to the warehouse and place them as follows:\n\nThis way, the maximum difference between any two adjacent cells in the grid is $4$, and exactly $11$ comics are used.\n\n## Input\n\nThe first line of input contains $t$, the number of test cases. Each test case begins with three integers $r$, $c$, and $k$, the number of rows of the warehouse, the number of columns of the warehouse, and the maximum number of comics Kakushi can bring in, respectively.$r$ lines then follow, each containing $c$ integers. The $j$th integer in the $i$th line denotes the number of comics at coordinate $(i, j)$, i.e. $A_((i comma j))$.\n\n## Output\n\nOutput one integer, the minimum instability obtainable by placing up to $k$ JUMP! comics in the warehouse stacks.\n\n[samples]\n\n## Scoring\n\n*For all subtasks*$1 <= A_{(i , j}) <= 10^(12)$$0 <= k <= 10^(18)$$1 <= r, c, r c <= 10^5$The sum of the $r c$'s in a single file is $<= 4 dot.op 10^5$$1 <= t <= 10$$r c > 1$*Subtask 1* (5 points):$k = 0$*Subtask 2* (10 points):$r, c, r c, k <= 200$*Subtask 3* (15 points):$r, c, r c <= 200$*Subtask 4* (15 points):$r, c, r c <= 3000$*Subtask 5* (20 points):$r = 1$ or $c = 1$*Subtask 6* (20 points):$r c <= 30000$The sum of the $r c$'s in a single file is $<= 60000$*Subtask 7* (15 points):No additional constraints.\n\n## Note\n\n_Note:_ The sample case is not valid for the first and fifth subtasks. It is valid for the other subtasks.The warehouse has $r = 3$ rows and $c = 5$ columns. Kakushi can bring in up to $k = 12$ JUMP! comics. The warehouse initially looks like the following:  Kakushi can choose to bring in $11$ comics to the warehouse and place them as follows:  This way, the maximum difference between any two adjacent cells in the grid is $4$, and exactly $11$ comics are used.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ t \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, t\\} $:  \n- Let $ n_k \\in \\mathbb{Z} $ be the number of banana pieces.  \n- Let $ c_k \\in \\mathbb{Z} $ be the fixed constant.  \n- Let $ A_k = (a_{k,1}, a_{k,2}, \\dots, a_{k,n_k}) $ be a sequence of positive integers, where $ a_{k,i} $ is the length of the $ i $-th banana piece.  \n\n**Constraints**  \n1. $ 1 \\le t \\le 10^5 $  \n2. $ 1 \\le n_k \\le 10^5 $ for each $ k $  \n3. $ 1 \\le c_k \\le 10^6 $ for each $ k $  \n4. $ 1 \\le a_{k,i} \\le 10^{18} $ for each $ k, i $  \n5. $ a_{k,i} \\cdot c_k^2 \\le 10^{18} $ for each $ k, i $  \n6. $ \\sum_{k=1}^{t} n_k \\le 10^5 $  \n\n**Objective**  \nYou may perform any number of operations:  \n- Select a banana piece of length $ b $, and split it into two pieces of positive integer lengths $ b_1, b_2 $ such that $ b_1 + b_2 = b $.  \n- Earn $ b_1 b_2 (b_1 + b_2 - c_k) = b_1 b_2 (b - c_k) $ pesos.  \n\nThe game ends when no further splits are possible (i.e., all pieces have length 1).  \n\nMaximize the total earnings over all possible sequences of splits.  \n\nLet $ S_k $ be the maximum total earnings for test case $ k $.  \nOutput $ S_k \\mod (10^9 + 7) $ for each test case.  \n\n**Note**: The splitting process is independent across pieces. The total maximum earnings is the sum of maximum earnings obtainable from each initial banana piece.  \n\nFor a single banana piece of initial length $ a $, define $ f(a) $ as the maximum total earnings obtainable by recursively splitting it until all pieces are of length 1. Then:  \n$$\nS_k = \\sum_{i=1}^{n_k} f(a_{k,i})\n$$  \n\nThe function $ f $ satisfies the recurrence:  \n$$\nf(1) = 0\n$$  \n$$\nf(b) = \\max_{\\substack{1 \\le b_1 < b \\\\ b_2 = b - b_1}} \\left\\{ b_1 b_2 (b - c_k) + f(b_1) + f(b_2) \\right\\} \\quad \\text{for } b > 1\n$$  \n\nHowever, due to the structure of the reward function, the optimal strategy is to split each piece into 1 and $ b-1 $ at every step, yielding:  \n$$\nf(b) = (b-1)(b - c_k) + f(1) + f(b-1) = (b-1)(b - c_k) + f(b-1)\n$$  \n\nThus, $ f(b) $ is the sum over all splits from $ b $ down to 2:  \n$$\nf(b) = \\sum_{x=2}^{b} (x-1)(x - c_k)\n$$  \n\nLet $ g(b) = \\sum_{x=2}^{b} (x-1)(x - c_k) $. Then:  \n$$\ng(b) = \\sum_{x=1}^{b-1} x(x + 1 - c_k) = \\sum_{x=1}^{b-1} \\left( x^2 + (1 - c_k)x \\right)\n$$  \n\nUsing closed-form formulas:  \n$$\ng(b) = \\frac{(b-1)b(2b-1)}{6} + (1 - c_k) \\cdot \\frac{(b-1)b}{2}\n$$  \n\nTherefore, for each banana piece of length $ a $:  \n$$\nf(a) = \\frac{(a-1)a(2a-1)}{6} + (1 - c) \\cdot \\frac{(a-1)a}{2}\n$$  \n\nFinal objective:  \n$$\n\\boxed{S_k = \\sum_{i=1}^{n_k} \\left[ \\frac{(a_i-1)a_i(2a_i-1)}{6} + (1 - c) \\cdot \\frac{(a_i-1)a_i}{2} \\right] \\mod (10^9 + 7)}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10268C","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}