CF1630D Flipping Range

You are given an array $ a $ of $ n $ integers and a set $ B $ of $ m $ positive integers such that $ 1 \leq b_i \leq \lfloor \frac{n}{2} \rfloor $ for $ 1\le i\le m $ , where $ b_i $ is the $ i $ -th element of $ B $ . You can make the following operation on $ a $ : 1. Select some $ x $ such that $ x $ appears in $ B $ . 2. Select an interval from array $ a $ of size $ x $ and multiply by $ -1 $ every element in the interval. Formally, select $ l $ and $ r $ such that $ 1\leq l\leq r \leq n $ and $ r-l+1=x $ , then assign $ a_i:=-a_i $ for every $ i $ such that $ l\leq i\leq r $ . Consider the following example, let $ a=[0,6,-2,1,-4,5] $ and $ B=\{1,2\} $ : 1. $ [0,6,-2,-1,4,5] $ is obtained after choosing size $ 2 $ and $ l=4 $ , $ r=5 $ . 2. $ [0,6,2,-1,4,5] $ is obtained after choosing size $ 1 $ and $ l=3 $ , $ r=3 $ . Find the maximum $ \sum\limits_{i=1}^n {a_i} $ you can get after applying such operation any number of times (possibly zero).

N/A

N/A

In the first test, you can apply the operation $ x=1 $ , $ l=3 $ , $ r=3 $ , and the operation $ x=1 $ , $ l=5 $ , $ r=5 $ , then the array becomes $ [0, 6, 2, 1, 4, 5] $ . In the second test, you can apply the operation $ x=2 $ , $ l=2 $ , $ r=3 $ , and the array becomes $ [1, 1, -1, -1, 1, -1, 1] $ , then apply the operation $ x=2 $ , $ l=3 $ , $ r=4 $ , and the array becomes $ [1, 1, 1, 1, 1, -1, 1] $ . There is no way to achieve a sum bigger than $ 5 $ .