codeforces-scrape

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

1061B.md (2050B)


      1 Source: https://codeforces.com/problemset/problem/1061/B
      2 
      3 B. Views Matter
      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 came to the exhibition and one exhibit has drawn your attention. It consists of $n$ stacks of blocks, where the $i$-th stack consists of $a_i$ blocks resting on the surface.
     22 
     23 The height of the exhibit is equal to $m$. Consequently, the number of blocks in each stack is less than or equal to $m$.
     24 
     25 There is a camera on the ceiling that sees the top view of the blocks and a camera on the right wall that sees the side view of the blocks.
     26 
     27 ![](https://espresso.codeforces.com/4a36a312cd84f277a7907d0e9b9443145ab8ed6a.png)
     28 
     29 Find the maximum number of blocks you can remove such that the views for both the cameras would not change.
     30 
     31 Note, that while originally all blocks are stacked on the floor, it is not required for them to stay connected to the floor after some blocks are removed. There is no gravity in the whole exhibition, so no block would fall down, even if the block underneath is removed. It is not allowed to move blocks by hand either.
     32 
     33 Input
     34 
     35 The first line contains two integers $n$ and $m$ ($1 \le n \le 100\,000$, $1 \le m \le 10^9$) — the number of stacks and the height of the exhibit.
     36 
     37 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le m$) — the number of blocks in each stack from left to right.
     38 
     39 Output
     40 
     41 Print exactly one integer — the maximum number of blocks that can be removed.
     42 
     43 Examples
     44 
     45 Input
     46 
     47 ```
     48 5 6  
     49 3 3 3 3 3
     50 ```
     51 
     52 Output
     53 
     54 ```
     55 10
     56 ```
     57 
     58 Input
     59 
     60 ```
     61 3 5  
     62 1 2 4
     63 ```
     64 
     65 Output
     66 
     67 ```
     68 3
     69 ```
     70 
     71 Input
     72 
     73 ```
     74 5 5  
     75 2 3 1 4 4
     76 ```
     77 
     78 Output
     79 
     80 ```
     81 9
     82 ```
     83 
     84 Input
     85 
     86 ```
     87 1 1000  
     88 548
     89 ```
     90 
     91 Output
     92 
     93 ```
     94 0
     95 ```
     96 
     97 Input
     98 
     99 ```
    100 3 3  
    101 3 1 1
    102 ```
    103 
    104 Output
    105 
    106 ```
    107 1
    108 ```
    109 
    110 Note
    111 
    112 The following pictures illustrate the first example and its possible solution.
    113 
    114 Blue cells indicate removed blocks. There are $10$ blue cells, so the answer is $10$.
    115 
    116 ![](https://espresso.codeforces.com/efc231ba97eb8dbe6280be58c9557ed80bf55f78.png)