{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cp\u003eIt is a sunny day in spring and you are about to meet\n Patrick, a close friend and former partner in crime. Patrick\n lost most of his money betting on programming contests, so he\n needs to pull off another job. For this he needs your help,\n even though you have retired from a life of crime. You are\n reluctant at first, as you have no desire to return to your old\n criminal ways, but you figure there is no harm in listening to\n his plan.\u003c/p\u003e\n\n \u003cp\u003eThere is a shipment of expensive consumer widgets in a\n nearby warehouse and Patrick intends to steal as much of it as\n he can. This entails finding a way into the building,\n incapacitating security guards, passing through various arrays\n of laser beams – you know, the usual heist techniques. However,\n the heart of the warehouse has been equipped with a security\n system that Patrick cannot disable. This is where he needs your\n help.\u003c/p\u003e\n\n \u003cp\u003eThe shipment is stored in large cubical crates, all of which\n have the same dimensions. The crates are stacked in neat piles,\n forming a three-dimensional grid. The security system takes\n pictures of the piles once per hour using three cameras: a\n front camera, a side camera and a top camera. The image from\n the front camera shows the height of the tallest pile in each\n column, the image from the side camera shows the height of the\n tallest pile in each row, and the image from the top camera\n shows whether or not each pile is empty. If the security system\n detects a change in any of the images, it sounds an alarm.\u003c/p\u003e\n\n \u003cp\u003eOnce Patrick is inside, he will determine the heights of the\n piles and send them to you. Figure\u0026nbsp;1 shows a possible\n layout of the grid and the view from each of the cameras.\u003c/p\u003e\n\n \u003cdiv id\u003d\"fig:initial\" class\u003d\"figure\"\u003e\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/aa50e386e2e3877178256ac5f132f45a?v\u003d1716157612\" alt\u003d\"\\includegraphics[width\u003d0.875\\textwidth ]{fig-1.pdf}\" style\u003d\"width:87.50%\"\u003e\n\n \u003cdiv class\u003d\"caption\"\u003e\n \u003cb\u003eFigure 1\u003c/b\u003e: Grid of heights and the corresponding\n camera views.\n \u003c/div\u003e\n \u003c/center\u003e\n \u003c/div\u003e\n\n \u003cdiv id\u003d\"fig:final\" class\u003d\"figure\"\u003e\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/fc4dca0eee2f4f4a5ddeada0b1770768?v\u003d1716157612\" alt\u003d\"\\includegraphics[width\u003d0.14\\textwidth ]{fig-final.pdf}\" style\u003d\"width:14.00%\"\u003e\n\n \u003cdiv class\u003d\"caption\"\u003e\n \u003cb\u003eFigure 2\u003c/b\u003e: Possible grid of heights after the heist\n \u003c/div\u003e\n \u003c/center\u003e\n \u003c/div\u003e\n\n \u003cp\u003ePatrick wants to steal as many crates as possible. Since he\n cannot disable the security system, he plans to fool it by\n arranging the remaining crates into piles so that the next set\n of camera images are the same. In the above example, it is\n possible to steal nine crates. Figure\u0026nbsp;2 shows one possible\n post-heist configuration that appears identical to the security\n system.\u003c/p\u003e\n\n \u003cp\u003ePatrick asks you to help him determine the maximum number of\n crates that can be stolen while leaving a configuration of\n crates that will fool the security system. Will you help him\n pull off this final job?\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe first line of input contains two integers \u003cspan class\u003d\"tex2jax_process\"\u003e$r$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\le r \\le 100$\u003c/span\u003e) and \u003cspan class\u003d\"tex2jax_process\"\u003e$c$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\le c \\le 100$\u003c/span\u003e), the number of rows and columns in the\n grid, respectively. Each of the following \u003cspan class\u003d\"tex2jax_process\"\u003e$r$\u003c/span\u003e lines contains \u003cspan class\u003d\"tex2jax_process\"\u003e$c$\u003c/span\u003e integers, the heights (in crates)\n of the piles in the corresponding row. All heights are between\n \u003cspan class\u003d\"tex2jax_process\"\u003e$0$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$10^9$\u003c/span\u003e inclusive.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eDisplay the maximum number of crates that can be stolen\n without being detected.\u003c/p\u003e\n\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 5\n1 4 0 5 2\n2 1 2 0 1\n0 2 3 4 4\n0 3 0 3 1\n1 2 2 1 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e9\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2 3\n50 20 3\n20 10 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e30\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}