{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp\u003eBeing a completist and a simplest, kid Yang Zhe cannot solve but\r\n get Wrong Answer from most of the OI problems. And he refuse to\r\n write two program of same kind at all. So he always fails in\r\n contests.\r\n\r\n\u003c/p\u003e\u003cp\u003eWhen having a contest, Yang Zhe looks at the score of every\r\n problems first. For the problems of the same score, Yang Zhe will\r\n do only one of them. If he\u0027s lucky enough, he can get all the scores\r\n wanted.\r\n\r\n\u003c/p\u003e\u003cp\u003eAmber is going to hold a contest in SPOJ. She has made a list of\r\n \u003ci\u003eN\u003c/i\u003e candidate problems, which fit Yang Zhe very well. So Yang\r\n Zhe can solve any problem he want. Amber lined up the problems,\r\n began to select. She will select a subsequence of the list as the\r\n final problems. Being A girl of great compassion, she\u0027d like to\r\n select such a subsequence (can be empty) that Yang Zhe will get the\r\n maximal score over all the possible subsequences.\r\n\r\n\u003c/p\u003e\u003cp\u003eAmber found the subsequence easily after a few minutes. To make\r\n things harder, Amber decided that, Yang Zhe can take this contest\r\n only if Yang Zhe can answer her \u003ci\u003eQ\u003c/i\u003e questions. The question is:\r\n if the final problems are limited to be a subsequence\r\n of \u003ci\u003elist\u003c/i\u003e[\u003ci\u003eX\u003c/i\u003e..\u003ci\u003eY\u003c/i\u003e] (1 \u0026lt;\u003d \u003ci\u003eX\u003c/i\u003e \u0026lt;\u003d \u003ci\u003eY\u003c/i\u003e \u0026lt;\u003d N),\r\n what\u0027s the maximal possible score Yang Zhe can get?\r\n\r\n\u003c/p\u003e\u003cp\u003eAs we know, Yang Zhe is a bit idiot (so why did he solve the\r\n problem with a negative score?), he got Wrong Answer again... Tell\r\n him the correct answer!\r\n\r\n\u003c/p\u003e\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cul\u003e\r\n \u003cli\u003eLine 1: integer \u003ci\u003eN\u003c/i\u003e (1 \u0026lt;\u003d \u003ci\u003eN\u003c/i\u003e \u0026lt;\u003d 100000);\r\n \u003c/li\u003e\u003cli\u003eLine 2: \u003ci\u003eN\u003c/i\u003e integers denoting the score of each problem,\r\n each of them is a integer in range [-100000, 100000];\r\n \u003c/li\u003e\u003cli\u003eLine 3: integer \u003ci\u003eQ\u003c/i\u003e (1 \u0026lt;\u003d \u003ci\u003eQ\u003c/i\u003e \u0026lt;\u003d 100000);\r\n \u003c/li\u003e\u003cli\u003eLine 3+\u003ci\u003ei\u003c/i\u003e (1 \u0026lt;\u003d \u003ci\u003ei\u003c/i\u003e \u0026lt;\u003d \u003ci\u003eQ\u003c/i\u003e): two\r\n integers \u003ci\u003eX\u003c/i\u003e and\r\n \u003ci\u003eY\u003c/i\u003e denoting the \u003ci\u003ei\u003c/i\u003eth question.\r\n\u003c/li\u003e\u003c/ul\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cul\u003e\r\n \u003cli\u003eLine \u003ci\u003ei\u003c/i\u003e: a single integer, the answer to the \u003ci\u003ei\u003c/i\u003eth\r\n question.\r\n\u003c/li\u003e\u003c/ul\u003e\r\n\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\r\n\u003cdiv\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\u003e9\r\n4 -2 -2 3 -1 -4 2 2 -6\r\n3\r\n1 2\r\n1 5\r\n4 9\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\n5\r\n3\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\r\n\u003cb\u003eWarning: large input/output data, be careful with certain languages\u003c/b\u003e\n\u003c/div\u003e"}}]}