codeforces-scrape

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

1139B.md (1620B)


      1 Source: https://codeforces.com/problemset/problem/1139/B
      2 
      3 B. Chocolates
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You went to the store, selling $n$ types of chocolates. There are $a_i$ chocolates of type $i$ in stock.
     22 
     23 You have unlimited amount of cash (so you are not restricted by any prices) and want to buy as many chocolates as possible. However if you buy $x_i$ chocolates of type $i$ (clearly, $0 \le x_i \le a_i$), then for all $1 \le j \lt i$ at least one of the following must hold:
     24 
     25 * $x_j = 0$ (you bought zero chocolates of type $j$)
     26 * $x_j \lt x_i$ (you bought less chocolates of type $j$ than of type $i$)
     27 
     28 For example, the array $x = [0, 0, 1, 2, 10]$ satisfies the requirement above (assuming that all $a_i \ge x_i$), while arrays $x = [0, 1, 0]$, $x = [5, 5]$ and $x = [3, 2]$ don't.
     29 
     30 Calculate the maximum number of chocolates you can buy.
     31 
     32 Input
     33 
     34 The first line contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$), denoting the number of types of chocolate.
     35 
     36 The next line contains $n$ integers $a_i$ ($1 \le a_i \le 10^9$), denoting the number of chocolates of each type.
     37 
     38 Output
     39 
     40 Print the maximum number of chocolates you can buy.
     41 
     42 Examples
     43 
     44 Input
     45 
     46 ```
     47 5
     48 1 2 1 3 6
     49 ```
     50 
     51 Output
     52 
     53 ```
     54 10
     55 ```
     56 
     57 Input
     58 
     59 ```
     60 5
     61 3 2 5 4 10
     62 ```
     63 
     64 Output
     65 
     66 ```
     67 20
     68 ```
     69 
     70 Input
     71 
     72 ```
     73 4
     74 1 1 1 1
     75 ```
     76 
     77 Output
     78 
     79 ```
     80 1
     81 ```
     82 
     83 Note
     84 
     85 In the first example, it is optimal to buy: $0 + 0 + 1 + 3 + 6$ chocolates.
     86 
     87 In the second example, it is optimal to buy: $1 + 2 + 3 + 4 + 10$ chocolates.
     88 
     89 In the third example, it is optimal to buy: $0 + 0 + 0 + 1$ chocolates.