plusminus
Given is array (s1, ..., sn) of length n. Sign si is + or -. Given is array of n + 1 numbers (a1, ..., an+ 1).
You need to put numbers between signs so that solution of this expression is maximal. You need to find value val defined as:
val = max{ap(1) s1 ... ap(n) sn ap(n + 1) | p is a permutation of numbers from 1 to n + 1.
InputIn first row of standard input is natural number n (1 <= n <= 100000). In second row are n signs s1 to sn. Every sign is '+' or '-'. Signs are not separated with empty space. In third row are n + 1 numbers: a1 to an + 1, separated with empty space. All this numbers are from interval [0, 1000000].
OutputIn first and only row of standard output, You need to write this maximal value val.
Input:
Output:
Explanation:
This is the only one solution
2+3-1+4
3
+-+
1 2 3 4Output:
8Explanation:
This is the only one solution
2+3-1+4
Input:
Output:
Explanation:
Every permutation of numbers gives optimal answer.
2
++
1 3 2Output:
6Explanation:
Every permutation of numbers gives optimal answer.
Input:
Output:
Explanation:
Every permutation with 12 on first place is optimal.
4
----
3 12 1 2 0Output:
6Explanation:
Every permutation with 12 on first place is optimal.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.