codeforces-scrape

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

1958D.md (2208B)


      1 Source: https://codeforces.com/problemset/problem/1958/D
      2 
      3 D. Staircase
      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 There is a staircase consisting of $n$ steps. Each step is either intact, or broken. For each broken step, an integer $a_i$ is given denoting the difficulty of repairing it.
     22 
     23 Every day, you can either:
     24 
     25 * repair an arbitrary broken step. The effort it takes to repair the $i$-th step is equal to $a_i$;
     26 * or repair two adjacent broken steps. The effort it takes to repair both the $i$-th step and the $(i+1)$-th step is equal to $2 \cdot (a_i+a_{i+1})$.
     27 
     28 You want to repair all broken steps of the staircase, and you want to do it in the minimum possible number of days. What is the minimum total effort it will take to repair all broken steps in the minimum number of days?
     29 
     30 Input
     31 
     32 The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     33 
     34 Each test case consists of two lines:
     35 
     36 * the first line contains one integer $n$ ($1 \le n \le 3 \cdot 10^5$) — the number of steps;
     37 * the second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^8$). If $a_i = 0$, then the $i$-th step does not need to be repaired; otherwise, the $i$-th step is broken and $a_i$ is the difficulty of repairing it.
     38 
     39 Additional constraint on the input: the sum of values of $n$ does not exceed $3 \cdot 10^5$.
     40 
     41 Output
     42 
     43 For each test case, print one integer — the minimum possible total effort it will take to repair all broken steps in the minimum number of days.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 6
     51 
     52 5
     53 
     54 0 0 0 0 0
     55 
     56 4
     57 
     58 0 13 15 8
     59 
     60 4
     61 
     62 13 15 0 8
     63 
     64 8
     65 
     66 1 2 3 4 5 6 7 8
     67 
     68 5
     69 
     70 99999999 100000000 99999999 99999999 99999999
     71 
     72 5
     73 
     74 2 3 4 3 2
     75 ```
     76 
     77 Output
     78 
     79 ```
     80 0
     81 59
     82 64
     83 72
     84 899999993
     85 24
     86 ```
     87 
     88 Note
     89 
     90 In the first test case, you don't have to do anything.
     91 
     92 In the second test case, you can repair the $3$-rd and the $4$-th step during the first day, and the $2$-nd step during the second day. The total effort will be $2 \cdot (15 + 8) + 13 = 59$.
     93 
     94 In the third test case, you can repair the $4$-th step during the first day, and two first steps during the second day. The total effort will be $8 + 2 \cdot (13 + 15) = 64$.