codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2062C.md (1705B)


      1 Source: https://codeforces.com/problemset/problem/2062/C
      2 
      3 C. Cirno and Operations
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Cirno has a sequence $a$ of length $n$. She can perform either of the following two operations for any (possibly, zero) times unless the current length of $a$ is $1$:
     22 
     23 * Reverse the sequence. Formally, $[a_1,a_2,\ldots,a_n]$ becomes $[a_n,a_{n-1},\ldots,a_1]$ after the operation.
     24 * Replace the sequence with its difference sequence. Formally, $[a_1,a_2,\ldots,a_n]$ becomes $[a_2-a_1,a_3-a_2,\ldots,a_n-a_{n-1}]$ after the operation.
     25 
     26 Find the maximum possible sum of elements of $a$ after all operations.
     27 
     28 Input
     29 
     30 The first line of input contains a single integer $t$ ($1 \leq t \leq 100$) — the number of input test cases.
     31 
     32 The first line of each test case contains a single integer $n$ ($1\le n\le 50$) — the length of sequence $a$.
     33 
     34 The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($|a_i|\le 1000$) — the sequence $a$.
     35 
     36 Output
     37 
     38 For each test case, print an integer representing the maximum possible sum.
     39 
     40 Example
     41 
     42 Input
     43 
     44 ```
     45 5
     46 
     47 1
     48 
     49 -1000
     50 
     51 2
     52 
     53 5 -3
     54 
     55 2
     56 
     57 1000 1
     58 
     59 9
     60 
     61 9 7 9 -9 9 -8 7 -8 9
     62 
     63 11
     64 
     65 678 201 340 444 453 922 128 987 127 752 0
     66 ```
     67 
     68 Output
     69 
     70 ```
     71 -1000
     72 8
     73 1001
     74 2056
     75 269891
     76 ```
     77 
     78 Note
     79 
     80 In the first test case, Cirno can not perform any operation, so the answer is $-1000$.
     81 
     82 In the second test case, Cirno firstly reverses the sequence, then replaces the sequence with its difference sequence: $[5,-3]\to[-3,5]\to[8]$. It can be proven that this maximizes the sum, so the answer is $8$.
     83 
     84 In the third test case, Cirno can choose not to operate, so the answer is $1001$.