{"raw_statement":[{"iden":"statement","content":"*The motivating story and definition of a rectilinear path (and related terms) are the same in Mondridalgo (Verification) and (Optimization). Skip to the bolded text for the first section where the two differ.*\n\nBob created a magnificent painting this year in the Mondridalgo style (a combination of Piet Mondrian's rectangles and Felix Hidalgo's neoclassicism), which both Alice and Cindy adore. Unfortunately, when Cindy asked him if she could keep the painting, he was too lovestruck and immediately said yes... forgetting that he had already previously promised the painting to Alice! Oh no! Remember everyone—don't be like Bob.\n\nUnable to choose between his two friends, Bob decides the best way to resolve this situation is to cut up his painting into two contiguous pieces using a pair of scissors, and then hand one piece to Alice and the other Cindy. That way, each of his friends is equally unhappy.\n\nWe formalize \"cutting with scissors\" by defining a _rectilinear path_ to be a non-empty sequence of \"cuts\" such that: \n\nOur goal is to try to find a partition which is not \"lop-sided\"—that is, neither one of Alice nor Cindy should be significantly happier than the other in this interaction. This partition also shouldn't be too complicated.\n\nFormally, given an integer $k$, find any partition whose valid rectilinear path uses at least $1$ and at most $k$ cuts, and which minimizes the value $| \"Alice ' s happiness\"-\"Cindy ' s happiness\"|$ among such partitions.\n\nThe first line of input contains the three space-separated integers $r$ and $c$ and $k$.\n\nThen, an $r times c$ grid follows, describing the Alice adoration ratings—that is, $r$ lines follow, each containing $c$ integers: $$ \\begin{array}{cccc} u_{1, 1} & u_{1, 2} & \\dots & u_{1, c} \\\\ u_{2, 1} & u_{2, 2} & \\dots & u_{2, c} \\\\ \\vdots & \\vdots & \\ddots & \\vdots \\\\ u_{r, 1} & u_{r, 2} & \\dots & u_{r, c} \\end{array} $$ where $u_(i comma j)$ is the Alice adoration rating of the square in the $i$th row from the top and $j$th column from the left.\n\nThen, another $r times c$ grid follows, describing the Cindy cherish ratings—that is, $r$ lines follow, each containing $c$ integers: $$ \\begin{array}{cccc} v_{1, 1} & v_{1, 2} & \\dots & v_{1, c} \\\\ v_{2, 1} & v_{2, 2} & \\dots & v_{2, c} \\\\ \\vdots & \\vdots & \\ddots & \\vdots \\\\ v_{r, 1} & v_{r, 2} & \\dots & v_{r, c} \\end{array} $$ where $v_(i comma j)$ is the Cindy cherish rating of the square in the $i$th row from the top and $j$th column from the left.\n\nOutput a single positive integer—the minimal value of $| \"Alice ' s happiness\"-\"Cindy ' s happiness\"|$.\n\n$$\\begin{align*}&\\begin{array}{|l|} \\hline \\text{Constraints For All Subtasks} \\\\ \\hline 2 \\leq r, c \\leq 6 \\\\ 1 \\leq k \\leq 6 \\\\ \\text{$-10^9 \\leq u_{i, j}, v_{i, j} \\leq 10^9$ for each $i, j$} \\\\ \\hline \\end{array}\\\\&\\begin{array}{|c|c|l|} \\hline \\text{Subtask} & \\text{Points} & \\text{Constraints} \\\\ \\hline 1 & \\mathbf{20} & k=1 \\\\ \\hline 2 & \\mathbf{30} & k \\leq 2 \\\\ \\hline 3 & \\mathbf{20} & r, c \\leq 3 \\\\ \\hline 4 & \\mathbf{20} & r, c \\leq 4 \\\\ \\hline 5 & \\mathbf{10} & \\text{No further constraints.} \\\\ \\hline \\end{array}\\\\\\end{align*}$$\n\nHere are the corresponding partitions for the first three sample inputs. \n\n"},{"iden":"input","content":"The first line of input contains the three space-separated integers $r$ and $c$ and $k$.Then, an $r times c$ grid follows, describing the Alice adoration ratings—that is, $r$ lines follow, each containing $c$ integers: $$ \\begin{array}{cccc} u_{1, 1} & u_{1, 2} & \\dots & u_{1, c} \\\\ u_{2, 1} & u_{2, 2} & \\dots & u_{2, c} \\\\ \\vdots & \\vdots & \\ddots & \\vdots \\\\ u_{r, 1} & u_{r, 2} & \\dots & u_{r, c} \\end{array} $$ where $u_(i comma j)$ is the Alice adoration rating of the square in the $i$th row from the top and $j$th column from the left.Then, another $r times c$ grid follows, describing the Cindy cherish ratings—that is, $r$ lines follow, each containing $c$ integers: $$ \\begin{array}{cccc} v_{1, 1} & v_{1, 2} & \\dots & v_{1, c} \\\\ v_{2, 1} & v_{2, 2} & \\dots & v_{2, c} \\\\ \\vdots & \\vdots & \\ddots & \\vdots \\\\ v_{r, 1} & v_{r, 2} & \\dots & v_{r, c} \\end{array} $$ where $v_(i comma j)$ is the Cindy cherish rating of the square in the $i$th row from the top and $j$th column from the left."},{"iden":"output","content":"Output a single positive integer—the minimal value of $| \"Alice ' s happiness\"-\"Cindy ' s happiness\"|$."},{"iden":"scoring","content":"$$\\begin{align*}&\\begin{array}{|l|} \\hline \\text{Constraints For All Subtasks} \\\\ \\hline 2 \\leq r, c \\leq 6 \\\\ 1 \\leq k \\leq 6 \\\\ \\text{$-10^9 \\leq u_{i, j}, v_{i, j} \\leq 10^9$ for each $i, j$} \\\\ \\hline \\end{array}\\\\&\\begin{array}{|c|c|l|} \\hline \\text{Subtask} & \\text{Points} & \\text{Constraints} \\\\ \\hline 1 & \\mathbf{20} & k=1 \\\\ \\hline 2 & \\mathbf{30} & k \\leq 2 \\\\ \\hline 3 & \\mathbf{20} & r, c \\leq 3 \\\\ \\hline 4 & \\mathbf{20} & r, c \\leq 4 \\\\ \\hline 5 & \\mathbf{10} & \\text{No further constraints.} \\\\ \\hline \\end{array}\\\\\\end{align*}$$"},{"iden":"examples","content":"Input4 5 1\n20 -8 11 4 0\n-7 -5 12 9 -2\n12 12 -9 5 -2\n11 10 12 1 -2\n-9 -6 -9 -2 9\n15 22 -5 -6 9\n-1 21 -5 10 9\n-1 29 -5 10 9\nOutput10\nInput4 5 2\n20 -8 11 4 0\n-7 -5 12 9 -2\n12 12 -9 5 -2\n11 10 12 1 -2\n-9 -6 -9 -2 9\n15 22 -5 -6 9\n-1 21 -5 10 9\n-1 29 -5 10 9\nOutput1\nInput4 5 5\n20 -8 11 4 0\n-7 -5 12 9 -2\n12 12 -9 5 -2\n11 10 12 1 -2\n-9 -6 -9 -2 9\n15 22 -5 -6 9\n-1 21 -5 10 9\n-1 29 -5 10 9\nOutput0\nInput4 5 6\n20 -8 11 4 0\n-7 -5 12 9 -2\n12 12 -9 5 -2\n11 10 12 1 -2\n-9 -6 -9 -2 9\n15 22 -5 -6 9\n-1 21 -5 10 9\n-1 29 -5 10 9\nOutput0\n"},{"iden":"note","content":"Here are the corresponding partitions for the first three sample inputs.    For example, in the first sample input, Alice's happiness would be $20 + (-8) + 11 + 4 + 0 + (-7) + (-5) + 12 + 9 + (-2) + 11 + 10 + 12 + 1 + (-2) = 52$. Meanwhile, Cindy's happiness is $(-1) + 29 + (-5) + 10 + 9 = 42$. We can show that the difference of $| 52 -42 | = 10$ is minimal across all partitions that use one cut."}],"translated_statement":[{"iden":"statement","content":"*The motivating story and definition of a rectilinear path (and related terms) are the same in Mondridalgo (Verification) and (Optimization). Skip to the bolded text for the first section where the two differ.*\n\nBob created a magnificent painting this year in the Mondridalgo style (a combination of Piet Mondrian's rectangles and Felix Hidalgo's neoclassicism), which both Alice and Cindy adore. Unfortunately, when Cindy asked him if she could keep the painting, he was too lovestruck and immediately said yes... forgetting that he had already previously promised the painting to Alice! Oh no! Remember everyone—don't be like Bob.\n\nUnable to choose between his two friends, Bob decides the best way to resolve this situation is to cut up his painting into two contiguous pieces using a pair of scissors, and then hand one piece to Alice and the other Cindy. That way, each of his friends is equally unhappy.\n\nWe formalize \"cutting with scissors\" by defining a _rectilinear path_ to be a non-empty sequence of \"cuts\" such that: \n\nOur goal is to try to find a partition which is not \"lop-sided\"—that is, neither one of Alice nor Cindy should be significantly happier than the other in this interaction. This partition also shouldn't be too complicated.\n\nFormally, given an integer $k$, find any partition whose valid rectilinear path uses at least $1$ and at most $k$ cuts, and which minimizes the value $| \"Alice ' s happiness\"-\"Cindy ' s happiness\"|$ among such partitions.\n\nThe first line of input contains the three space-separated integers $r$ and $c$ and $k$.\n\nThen, an $r \\times c$ grid follows, describing the Alice adoration ratings—that is, $r$ lines follow, each containing $c$ integers: $$ \\begin{array}{cccc} u_{1, 1} & u_{1, 2} & \\dots & u_{1, c} \\\\ u_{2, 1} & u_{2, 2} & \\dots & u_{2, c} \\\\ \\vdots & \\vdots & \\ddots & \\vdots \\\\ u_{r, 1} & u_{r, 2} & \\dots & u_{r, c} \\end{array} $$ where $u_{i, j}$ is the Alice adoration rating of the square in the $i$th row from the top and $j$th column from the left.\n\nThen, another $r \\times c$ grid follows, describing the Cindy cherish ratings—that is, $r$ lines follow, each containing $c$ integers: $$ \\begin{array}{cccc} v_{1, 1} & v_{1, 2} & \\dots & v_{1, c} \\\\ v_{2, 1} & v_{2, 2} & \\dots & v_{2, c} \\\\ \\vdots & \\vdots & \\ddots & \\vdots \\\\ v_{r, 1} & v_{r, 2} & \\dots & v_{r, c} \\end{array} $$ where $v_{i, j}$ is the Cindy cherish rating of the square in the $i$th row from the top and $j$th column from the left.\n\nOutput a single positive integer—the minimal value of $| \"Alice ' s happiness\"-\"Cindy ' s happiness\"|$."},{"iden":"input","content":"The first line of input contains the three space-separated integers $r$ and $c$ and $k$.Then, an $r \\times c$ grid follows, describing the Alice adoration ratings—that is, $r$ lines follow, each containing $c$ integers: $$ \\begin{array}{cccc} u_{1, 1} & u_{1, 2} & \\dots & u_{1, c} \\\\ u_{2, 1} & u_{2, 2} & \\dots & u_{2, c} \\\\ \\vdots & \\vdots & \\ddots & \\vdots \\\\ u_{r, 1} & u_{r, 2} & \\dots & u_{r, c} \\end{array} $$ where $u_{i, j}$ is the Alice adoration rating of the square in the $i$th row from the top and $j$th column from the left.Then, another $r \\times c$ grid follows, describing the Cindy cherish ratings—that is, $r$ lines follow, each containing $c$ integers: $$ \\begin{array}{cccc} v_{1, 1} & v_{1, 2} & \\dots & v_{1, c} \\\\ v_{2, 1} & v_{2, 2} & \\dots & v_{2, c} \\\\ \\vdots & \\vdots & \\ddots & \\vdots \\\\ v_{r, 1} & v_{r, 2} & \\dots & v_{r, c} \\end{array} $$ where $v_{i, j}$ is the Cindy cherish rating of the square in the $i$th row from the top and $j$th column from the left."},{"iden":"output","content":"Output a single positive integer—the minimal value of $| \"Alice ' s happiness\"-\"Cindy ' s happiness\"|$."},{"iden":"scoring","content":"$$\\begin{align*}&\\begin{array}{|l|} \\hline \\text{Constraints For All Subtasks} \\\\ \\hline 2 \\leq r, c \\leq 6 \\\\ 1 \\leq k \\leq 6 \\\\ \\text{$-10^9 \\leq u_{i, j}, v_{i, j} \\leq 10^9$ for each $i, j$} \\\\ \\hline \\end{array}\\\\&\\begin{array}{|c|c|l|} \\hline \\text{Subtask} & \\text{Points} & \\text{Constraints} \\\\ \\hline 1 & \\mathbf{20} & k=1 \\\\ \\hline 2 & \\mathbf{30} & k \\leq 2 \\\\ \\hline 3 & \\mathbf{20} & r, c \\leq 3 \\\\ \\hline 4 & \\mathbf{20} & r, c \\leq 4 \\\\ \\hline 5 & \\mathbf{10} & \\text{No further constraints.} \\\\ \\hline \\end{array}\\\\\\end{align*}$$"},{"iden":"examples","content":"Input4 5 1\n20 -8 11 4 0\n-7 -5 12 9 -2\n12 12 -9 5 -2\n11 10 12 1 -2\n-9 -6 -9 -2 9\n15 22 -5 -6 9\n-1 21 -5 10 9\n-1 29 -5 10 9\nOutput10\nInput4 5 2\n20 -8 11 4 0\n-7 -5 12 9 -2\n12 12 -9 5 -2\n11 10 12 1 -2\n-9 -6 -9 -2 9\n15 22 -5 -6 9\n-1 21 -5 10 9\n-1 29 -5 10 9\nOutput1\nInput4 5 5\n20 -8 11 4 0\n-7 -5 12 9 -2\n12 12 -9 5 -2\n11 10 12 1 -2\n-9 -6 -9 -2 9\n15 22 -5 -6 9\n-1 21 -5 10 9\n-1 29 -5 10 9\nOutput0\nInput4 5 6\n20 -8 11 4 0\n-7 -5 12 9 -2\n12 12 -9 5 -2\n11 10 12 1 -2\n-9 -6 -9 -2 9\n15 22 -5 -6 9\n-1 21 -5 10 9\n-1 29 -5 10 9\nOutput0\n"},{"iden":"note","content":"Here are the corresponding partitions for the first three sample inputs.    For example, in the first sample input, Alice's happiness would be $20 + (-8) + 11 + 4 + 0 + (-7) + (-5) + 12 + 9 + (-2) + 11 + 10 + 12 + 1 + (-2) = 52$. Meanwhile, Cindy's happiness is $(-1) + 29 + (-5) + 10 + 9 = 42$. We can show that the difference of $| 52 -42 | = 10$ is minimal across all partitions that use one cut."}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ r, c, k \\in \\mathbb{Z}^+ $ with $ 2 \\leq r, c \\leq 6 $, $ 1 \\leq k \\leq 6 $.  \nLet $ U = (u_{i,j}) \\in \\mathbb{Z}^{r \\times c} $ be the Alice adoration grid.  \nLet $ V = (v_{i,j}) \\in \\mathbb{Z}^{r \\times c} $ be the Cindy cherish grid.  \n\nA *rectilinear path* is a sequence of axis-aligned unit-length cuts along grid edges, forming a connected path from one boundary of the grid to another, using at least 1 and at most $ k $ cuts, that partitions the grid into two non-empty contiguous regions $ A $ and $ B $.  \n\nFor a partition into regions $ A $ and $ B $:  \n- Alice’s happiness: $ H_A = \\sum_{(i,j) \\in A} u_{i,j} $,  \n- Cindy’s happiness: $ H_B = \\sum_{(i,j) \\in B} v_{i,j} $.  \n*(Note: The partition assigns region $ A $ to Alice and region $ B $ to Cindy.)*  \n\n**Constraints**  \n1. Each rectilinear path uses $ 1 \\leq p \\leq k $ cuts.  \n2. The path partitions the grid into exactly two non-empty, connected regions.  \n\n**Objective**  \nFind the partition minimizing:  \n$$\n\\left| \\sum_{(i,j) \\in A} u_{i,j} - \\sum_{(i,j) \\in B} v_{i,j} \\right|\n$$  \nover all valid rectilinear paths with $ 1 \\leq p \\leq k $ cuts.","simple_statement":null,"has_page_source":false}