{"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\u003eYou are the commander of a troop of n soldiers, numbered from 1 to n. For the battle ahead, you plan to divide these n soldiers into several commando units. To promote unity and boost morale, each unit will consist of a contiguous sequence of soldiers of the form (i, i+1 ... i+k).\u003c/p\u003e\r\n\u003cp\u003eEach soldier i has a battle effectiveness rating xi . Originally, the battle effectiveness x of a commando unit (i, i+1 ... i+k) was computed by adding up the individual battle effectiveness of the soldiers in the unit. In other words, x \u003d x\u003csub\u003ei\u003c/sub\u003e + x\u003csub\u003ei\u003c/sub\u003e+1 + ··· + x\u003csub\u003ei\u003c/sub\u003e+k .\u003c/p\u003e\r\n\u003cp\u003eHowever, years of glorious victories have led you to conclude that the battle effectiveness of a unit should be adjusted as follows: the adjusted effectiveness x is computed by using the equation x \u003d ax\u003csup\u003e2\u003c/sup\u003e + bx + c, where a, b, c are known coefficients(a \u0026lt; 0), x is the original effectiveness of the unit.\u003c/p\u003e\r\n\r\n\u003cp\u003eYour task as commander is to divide your soldiers into commando units in order to maximize the sum of the adjusted effectiveness of all the units.\u003c/p\u003e\r\n\r\n\u003cp\u003eFor instance, suppose you have 4 soldiers, x\u003csub\u003e1\u003c/sub\u003e \u003d 2, x\u003csub\u003e2\u003c/sub\u003e \u003d 2, x\u003csub\u003e3\u003c/sub\u003e \u003d 3, x\u003csub\u003e4\u003c/sub\u003e \u003d 4. Further, let the coefficients for the equation to adjust the battle effectiveness of a unit be a \u003d −1, b \u003d 10, c \u003d −20. In this case, the best solution is to divide the soldiers into three commando units: The first unit contains soldiers 1 and 2, the second unit contains soldier 3, and the third unit contains soldier 4. The battle effectiveness of the three units are 4, 3, 4 respectively, and the adjusted effectiveness are 4, 1, 4 respectively. The total adjusted effectiveness for this grouping is 9 and it can be checked that no better solution is possible.\u003c/p\u003e\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eFirst Line of input consists \u003cstrong\u003enumber of cases T\u003c/strong\u003e.\u003c/p\u003e\r\n\u003cp\u003eEach case consists of three lines. The first line contains a positive integer n, the total number of soldiers. The second line contains 3 integers a, b, and c, the coefficients for the equation to adjust the battle effectiveness of a commando unit. The last line contains n integers x1, x2 ... xn, separated by spaces, representing the battle effectiveness of soldiers 1, 2 ... n, respectively.\u003c/p\u003e\r\n\r\n\u003ch3\u003eConstraints\u003c/h3\u003e\r\n\u003cp\u003eT ≤ 3\u003c/p\u003e\r\n\u003cp\u003en ≤ 1, 000, 000\u003c/p\u003e\r\n\u003cp\u003e−5 ≤ a ≤ −1\u003c/p\u003e\r\n\u003cp\u003e|b| ≤ 10, 000, 000\u003c/p\u003e\r\n\u003cp\u003e|c| ≤ 10, 000, 000\u003c/p\u003e\r\n\u003cp\u003e1 ≤ xi ≤ 100\u003c/p\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eOutput each answer in a single line.\u003c/p\u003e\r\n\r\n\u003ch3\u003eSample\u003c/h3\u003e\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\u003e3\r\n4\r\n-1 10 -20\r\n2 2 3 4\r\n5\r\n-1 10 -20\r\n1 2 3 4 5\r\n8\r\n-2 4 3\r\n100 12 3 4 5 2 4 2\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e9\r\n13\r\n-19884\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\r\n\u003cp\u003e\u003cstrong\u003e(Official dataset of APIO was NOT used in this problem.)\u003c/strong\u003e\u003c/p\u003e\n\u003c/div\u003e"}}]}