{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003e Read problems statements in \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/OCT15/mandarin/JUMP.pdf\"\u003eMandarin Chinese \u003c/a\u003e and \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/OCT15/russian/JUMP.pdf\"\u003eRussian\u003c/a\u003e \u003c/h3\u003e\r\n\r\n\r\n\u003cp\u003e\r\nChef the chief is participating in a hill jumping competition.\r\n\u003c/p\u003e\r\n\u003cp\u003e\r\nThere are N hills arranged in a row, and each of them is assigned a unique index from 1 to \u003cb\u003eN\u003c/b\u003e — the \u003cb\u003ei\u003c/b\u003e\u003csup\u003eth\u003c/sup\u003e hill has an index \u003cb\u003eP\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e on it. The height of the \u003cb\u003ei\u003c/b\u003e\u003csup\u003eth\u003c/sup\u003e hill is \u003cb\u003eH\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e.\r\nChef starts at the first hill with a goal to reach the \u003cb\u003eN\u003csup\u003eth\u003c/sup\u003e\u003c/b\u003e hill by jumping over hills from left to right (he is not allowed to jump in the other direction), jumping from \u003cb\u003ei\u003c/b\u003e\u003csup\u003eth\u003c/sup\u003e hill to \u003cb\u003ej\u003c/b\u003e\u003csup\u003eth\u003c/sup\u003e costs (\u003cb\u003eH\u003csub\u003ej\u003c/sub\u003e\u003c/b\u003e - \u003cb\u003eH\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e)\u003csup\u003e2\u003c/sup\u003e energy.\r\n\u003c/p\u003e\r\n\u003cp\u003e\r\nWhen chief is on the \u003cb\u003ei\u003c/b\u003e\u003csup\u003eth\u003c/sup\u003e hill, he has to prepare a special dish for the community of that hill as a thanks for letting him use their resources. This will cost him \u003cb\u003eA\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e energy (some dishes are chief\u0027s favorites and preparing it refreshes chef that why \u003cb\u003eA\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e may be negative). To make things more challenging for Chef the chief, he is allowed to jump from \u003cb\u003ei\u003c/b\u003e\u003csup\u003eth\u003c/sup\u003e hill to \u003cb\u003ej\u003c/b\u003e\u003csup\u003eth\u003c/sup\u003e if and only if \u003cb\u003ei \u003c j\u003c/b\u003e and \u003cb\u003eP\u003csub\u003ei\u003c/sub\u003e \u003c P\u003csub\u003ej\u003c/sub\u003e\u003c/b\u003e.\r\n\u003c/p\u003e\r\n\u003cp\u003e\r\nHelp Chef choose the sequence of jumps that consume the minimum energy possible. (Note that it\u0027s possible at any moment that energy consumed is negative.)\r\n\u003c/p\u003e\r\n\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003e\r\nThe first line of input contains a single integer \u003cb\u003eN\u003c/b\u003e.\u003cbr /\u003e\r\nThe second line contains \u003cb\u003eN\u003c/b\u003e space-separated integers \u003cb\u003eP\u003csub\u003e1\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003eP\u003csub\u003e2\u003c/sub\u003e\u003c/b\u003e, ... , \u003cb\u003eP\u003csub\u003eN\u003c/sub\u003e\u003c/b\u003e.\u003cbr/\u003e\r\nThe third line contains \u003cb\u003eN\u003c/b\u003e space-separated integers \u003cb\u003eA\u003csub\u003e1\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003eA\u003csub\u003e2\u003c/sub\u003e\u003c/b\u003e, ... , \u003cb\u003eA\u003csub\u003eN\u003c/sub\u003e\u003c/b\u003e.\u003cbr/\u003e\r\nThe fourth line contains \u003cb\u003eN\u003c/b\u003e space-separated integers \u003cb\u003eH\u003csub\u003e1\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003eH\u003csub\u003e2\u003c/sub\u003e\u003c/b\u003e, ... , \u003cb\u003eH\u003csub\u003eN\u003c/sub\u003e\u003c/b\u003e.\u003cbr/\u003e\r\n\u003c/p\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eOutput a single line containing the answer to the problem i.e. the minimal possible amount of \u003cb\u003econsumed\u003c/b\u003e energy.\u003c/p\u003e\r\n\r\n\u003ch3\u003eConstraints\u003c/h3\u003e\r\n\u003cp\u003e\u003cul\u003e\r\n\u003cli\u003e\u003cb\u003e2\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e ≤ \u003cb\u003e3 × 10\u003csup\u003e5\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003eP\u003c/b\u003e is a permutation of the first \u003cb\u003eN\u003c/b\u003e integer numbers\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003eP\u003csub\u003e1\u003c/sub\u003e\u003d1\u003c/b\u003e and \u003cb\u003eP\u003csub\u003eN\u003c/sub\u003e\u003dN\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003e-10\u003csup\u003e9\u003c/sup\u003e\u003c/b\u003e ≤ \u003cb\u003eA\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ≤ \u003cb\u003e10\u003csup\u003e9\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eH\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ≤ \u003cb\u003e6 × 10\u003csup\u003e5\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\r\n\u003c/ul\u003e\u003c/p\u003e\r\n\r\n\u003ch3\u003eSubtasks\u003c/h3\u003e\r\n\u003cp\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e\u003cb\u003eSubtask 1\u003c/b\u003e (5 points) : \u003cb\u003e2\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e ≤ \u003cb\u003e20\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003eSubtask 2\u003c/b\u003e (15 points) : \u003cb\u003e2\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e ≤ \u003cb\u003e5000\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003eSubtask 3\u003c/b\u003e (20 points) : \u003cb\u003e2\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e ≤ \u003cb\u003e3 × 10\u003csup\u003e5\u003c/sup\u003e\u003c/b\u003e, \u003cb\u003eP\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e \u003d \u003cb\u003eH\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e \u003d \u003cb\u003ei\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003eSubtask 4\u003c/b\u003e (30 points) : \u003cb\u003e2\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e ≤ \u003cb\u003e3 × 10\u003csup\u003e5\u003c/sup\u003e\u003c/b\u003e, \u003cb\u003eH\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e \u003d \u003cb\u003ei\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003eSubtask 5\u003c/b\u003e (30 points) : original constraints\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/p\u003e\r\n\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cpre\u003e\u003cb\u003eInput:\u003c/b\u003e\r\n\u003ctt\u003e5\r\n1 4 3 2 5\r\n0 1 3 0 0\r\n1 2 3 4 5\u003c/tt\u003e\r\n\r\n\u003cb\u003eOutput:\u003c/b\u003e\r\n\u003ctt\u003e10\u003c/tt\u003e\r\n\r\n\u003c/pre\u003e\r\n\u003ch3\u003eExplanation\u003c/h3\u003e\r\n\u003cp\u003e\u003cb\u003eExample case 1.\u003c/b\u003e jumping from first hill to 4\u003csup\u003eth\u003c/sup\u003e one then to 5\u003csup\u003eth\u003c/sup\u003e; the answer will be 0 + 0 + 0 + (4-1)^2 + (5-4)^2 \u003d 10\u003c/p\u003e"}}]}