#P7052. Maximizing the Expression Value
Maximizing the Expression Value
Maximizing the Expression Value
Eva, a third‐grade student who has just learned arbitrary‐precision arithmetic, is given an expression as homework. The expression consists of non‑negative integers and the operators '+' and '-' (for addition and subtraction). Tired of the monotony of simple evaluation, Eva is allowed to insert additional '+' and '-' signs anywhere within the digits of any integer in the expression. However, the relative order of the digits and the original operators must remain unchanged.
The twist is: when a number is preceded by a minus sign, Eva can split the number into several parts so that instead of subtracting the whole number, she subtracts the sum of its individual digits. On the other hand, if a number is at the beginning of the expression or is preceded by a plus sign, the best strategy is to leave it unsplit, because the whole number is greater than the sum of its digits (if it has two or more digits).
Formally, you are given an expression of the form
where each Ni is a non‑negative integer (possibly with many digits) and each opi is either '+' or '-'. You are allowed to insert extra '+' or '-' signs inside any Ni to split it into several numbers. After the insertion, if a number is preceded by a minus sign, you may replace it with the sum of its digits (which is always smaller than or equal to the original number for numbers with at least two digits). If a number is preceded by a plus sign (or is the first number of the expression) then you should leave it intact. Your task is to compute the maximum possible value of the expression under these operations.
Note: Use \(\LaTeX\)
formatting for any formulas.
inputFormat
The input consists of a single line containing the expression S
. The expression includes digits (0-9) and the characters '+' and '-'.
It is guaranteed that S
is a valid expression. There are no spaces in the input.
outputFormat
Output a single line containing the maximum possible value of the expression after optimally inserting additional '+' and '-' signs.
sample
25-12
22