codeforces-scrape

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

604B.md (2159B)


      1 Source: https://codeforces.com/problemset/problem/604/B
      2 
      3 B. More Cowbell
      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 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Kevin Sun wants to move his precious collection of *n* cowbells from Naperthrill to Exeter, where there is actually grass instead of corn. Before moving, he must pack his cowbells into *k* boxes of a fixed size. In order to keep his collection safe during transportation, he won't place more than two cowbells into a single box. Since Kevin wishes to minimize expenses, he is curious about the smallest size box he can use to pack his entire collection.
     22 
     23 Kevin is a meticulous cowbell collector and knows that the size of his *i*-th (1 ≤ *i* ≤ *n*) cowbell is an integer *s**i*. In fact, he keeps his cowbells sorted by size, so *s**i* - 1 ≤ *s**i* for any *i* > 1. Also an expert packer, Kevin can fit one or two cowbells into a box of size *s* if and only if the sum of their sizes does not exceed *s*. Given this information, help Kevin determine the smallest *s* for which it is possible to put all of his cowbells into *k* boxes of size *s*.
     24 
     25 Input
     26 
     27 The first line of the input contains two space-separated integers *n* and *k* (1 ≤ *n* ≤ 2·*k* ≤ 100 000), denoting the number of cowbells and the number of boxes, respectively.
     28 
     29 The next line contains *n* space-separated integers *s*1, *s*2, ..., *s**n* (1 ≤ *s*1 ≤ *s*2 ≤ ... ≤ *s**n* ≤ 1 000 000), the sizes of Kevin's cowbells. It is guaranteed that the sizes *s**i* are given in non-decreasing order.
     30 
     31 Output
     32 
     33 Print a single integer, the smallest *s* for which it is possible for Kevin to put all of his cowbells into *k* boxes of size *s*.
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 2 1  
     41 2 5
     42 ```
     43 
     44 Output
     45 
     46 ```
     47 7
     48 ```
     49 
     50 Input
     51 
     52 ```
     53 4 3  
     54 2 3 5 9
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 9
     61 ```
     62 
     63 Input
     64 
     65 ```
     66 3 2  
     67 3 5 7
     68 ```
     69 
     70 Output
     71 
     72 ```
     73 8
     74 ```
     75 
     76 Note
     77 
     78 In the first sample, Kevin must pack his two cowbells into the same box.
     79 
     80 In the second sample, Kevin can pack together the following sets of cowbells: {2, 3}, {5} and {9}.
     81 
     82 In the third sample, the optimal solution is {3, 5} and {7}.