codeforces-scrape

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

2169C.md (1662B)


      1 Source: https://codeforces.com/problemset/problem/2169/C
      2 
      3 C. Range Operation
      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 You are given an integer array $a$ of length $n$.
     22 
     23 You can perform the following operation: choose a range $[l, r]$ ($1 \le l \le r \le n$) and replace the value of elements $a_l, a_{l+1}, \dots, a_r$ with $(l + r)$.
     24 
     25 Your task is to calculate the maximum possible total array sum if you can perform the aforementioned operation at most once.
     26 
     27 Input
     28 
     29 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     30 
     31 The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$).
     32 
     33 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 2n$).
     34 
     35 Additional constraint on the input: the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.
     36 
     37 Output
     38 
     39 For each test case, print a single integer — the maximum possible total array sum if you can perform the aforementioned operation at most once.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 4
     47 
     48 3
     49 
     50 2 5 1
     51 
     52 2
     53 
     54 4 4
     55 
     56 4
     57 
     58 1 3 2 1
     59 
     60 5
     61 
     62 3 2 0 9 10
     63 ```
     64 
     65 Output
     66 
     67 ```
     68 13
     69 
     70 8
     71 
     72 20
     73 
     74 32
     75 ```
     76 
     77 Note
     78 
     79 In the first example, you can perform the operation on the subarray $[3, 3]$, resulting in the array $[2, 5, 6]$ and the sum $13$.
     80 
     81 In the second example, you don't need to perform any operation.
     82 
     83 In the third example, you can perform the operation on the subarray $[1, 4]$, resulting in the array $[5, 5, 5, 5]$ and the sum $20$.
     84 
     85 In the fourth example, you can perform the operation on the subarray $[2, 3]$, resulting in the array $[3, 5, 5, 9, 10]$ and the sum $32$.