Log inSign up
Problems / B049

Harvesting salt

200 ptsCases 16Set by dongbinna
Added October 30.

Statement

A salt farm is divided into N sections, and salt is piled up in every section. The height of the pile is fixed for each section, and two sections may have the same height.

A scraper is used to bring the salt in. Set the scraper to height H and make one pass over the salt farm, and in a section whose pile is higher than H only the part above H is shaved off while the rest stays where it is. In a section whose pile is equal to H or lower than H, nothing comes off. The amount of salt that comes from a section is therefore the height of its pile minus H, and if that value is below 0, nothing comes off. The scraper makes only one pass, and it goes over every section at the same height.

The amount of salt that has to be delivered this year is fixed at M. The amount brought in must not fall below M, which pushes the scraper lower, but as much salt as possible should be left on the farm, so the scraper is set as high as it can be. The scraper height is set to an integer of 0 or more.

Write a program that, given the height of the salt piled in each section and the amount M that has to be delivered, finds the largest scraper height at which the amount brought in does not fall below M.

For example, suppose the heights of the salt piled in N=4 sections are as in the following table and the amount M that has to be delivered is 7.

Section1234
Pile height20151017

With the scraper at 15, section 1 gives 5 and section 4 gives 2. Section 2 has a pile equal to the scraper and section 3 is lower than the scraper, so nothing comes off either of them. The amount brought in is 7, which does not fall below the 7 that has to be delivered. Raising the scraper one step to 16 makes the amount brought in 5, which does fall below 7.

Scraper heightSection 1Section 2Section 3Section 4Amount brought in
1550027
1640015

The answer in this example is therefore 15. The lower the scraper goes, the more salt comes off, so it is enough to find the highest height at which the amount brought in does not fall below M.

Input and Output Examples

Example 1

Input

4 7
20 15 10 17

Output

15

Example 2

Input

5 20
4 42 40 26 46

Output

36

Example 3

Input

1 444
917

Output

473

Input

  • The number of sections N and the amount of salt M that has to be delivered are given first, in that order on the first line, separated by one space. N is a natural number from 1 to 1,000,000, and M is a natural number of 1 or more that is not larger than the sum of the pile heights over all of the sections.

  • The second line then holds the height of the salt piled in each section, from section 1 through section N in order, separated by one space. Each height is a natural number from 1 to 1,000,000,000.

Output

  • Print the largest scraper height at which the amount brought in does not fall below M on the first line.

  • Print one number and then a newline. Do not attach any other character or space before or after it.

Requirements

  • Read the input from standard input and write the answer to standard output
  • The scraper makes only one pass, and it goes over every section at the same height
  • Salt comes only from a section whose pile is higher than the scraper height, and the amount is that difference
  • The amount brought in must not fall below M, and among the heights that satisfy this the scraper height is set as large as possible
  • The amounts brought in can add up to far more than 1,000,000,000, so watch that the number does not overflow while you add them up
  • N goes up to 1,000,000, so raising the scraper height one step at a time from 0 does not finish in time
  • Grading compares the output with the expected value down to the last character
  • You must write a program that reads from standard input and writes to standard output
  • Trailing spaces at the end of a line and blank lines at the end of the output are ignored when grading
  • The languages you can use are Python and JavaScript
  • The memory limit is 256MB. The browser does not measure it, it only states it
  • The time limit is set by measuring the setter's reference solution on the same runtime
  • On this problem you submit code, not a prompt. That code runs in the browser on this device, and all that goes to the server is a fingerprint of the output and the time it took. Whether it is correct is decided by the server. The run time is a number each device reports, so the code and the device details are posted next to it on the leaderboard.
  • There are 16 cases, and 3 of them show the input together with the expected output. The rest are used only when you submit and are not shown on this page.
  • You have to pass all 16 cases to solve this.
Read the requirements carefully before solving. Tampering with the grading to make a submission look like a pass can get you sanctioned if caught. The code you submit is published on the leaderboard along with the result.

Examples

3 public cases. Judging also uses hidden cases. You have to pass all 16 cases to solve this.

Input
Expected output
1 444
917
473
4 7
20 15 10 17
15
5 20
4 42 40 26 46
36

Solution

Your code runs on this device. Only the fingerprint of the output and the elapsed time go to the server. The server decides whether it is correct.

0 chars1 lineMemory 256MB (recorded only)Reference 204ms

Submitting requires you to log in. Running against the public cases works without one.

You can test with 3 public cases. Submitting runs the hidden cases too.

People who solved this problem

Nobody yet. You could be the first.