Pouring Drinks (APCS 2024-10 Beginner)

Points 100 1.0s 256M

A cup's volume can be viewed as two stacked cuboids (see the figure below): the lower cuboid has base area \(w_1 \times w_1 ~\mathrm{cm^2}\) and height \(h_1 ~\mathrm{cm}\); the upper cuboid has base area \(w_2 \times w_2 ~\mathrm{cm^2}\) and height \(h_2 ~\mathrm{cm}\).

The cup starts empty. You pour drinks \(n\) times; each time you pour \(v ~\mathrm{cm^3}\). When the cup is full, the water level no longer rises. Find the maximum rise in water level among these \(n\) pours.

Input

The first line contains a positive integer \(n\), the number of pours.

The second line contains four positive integers \(w_1, w_2, h_1, h_2\), the cup's widths and heights.

The third line contains \(n\) positive integers, the volume of each pour.

Constraints

  • \(1 \le n \le 10\)
  • \(1 \le w_1, w_2, h_1, h_2 \le 50\)
  • It is guaranteed that the water-level rise after each pour is an integer

Output

Output the maximum water-level rise (in cm) among the \(n\) pours.

Scoring

The time limit for each test case is \(1\) second; your score is the sum over the test cases you pass. The subtasks are:

  • Subtask 1 (\(60\) points): \(n = 1\) (so the answer is the water level after pouring once).
  • Subtask 2 (\(40\) points): no constraints.

Sample Input 1

1
4 6 8 5
200

Sample Output 1

10

Sample Input 2

2
5 10 12 8
400 600

Sample Output 2

13

Sample Input 3

5
16 44 28 17
2560 1280 1536 1024 10448

Sample Output 3

10

Source

APCS programming exam, October 2024, Problem 1.

Problem page help

Keyboard shortcuts

Main features

  • Sample tests — Runs the sample cases bundled with the problem and auto-compares against the expected output.
  • Custom test — Run your code with your own stdin. Optionally tick the "Compare with expected (diff)" box to verify against expected output line-by-line.
  • Template — Paste the default code template you set on your profile page.
  • Collab — Edit this problem together with classmates in real time.
  • Auto-draft — Editor contents auto-save to your browser every 1.5 seconds (per account / problem / language).
  • Submit — Send your code to the judge for grading; returns AC / WA / TLE etc.

Limits

  • Source code: at most 65,536 characters
  • Custom test stdin and expected output: at most 1 MB each (≈1 million characters)
  • Custom test and sample test share the sandbox; about 1 request per 3 s per user (sample test: 1 per 1 s)
  • Custom test and sample test both have a 15 second wall-clock cap (the official judge still uses the problem time limit)
  • Interactive problems do not offer custom test (cannot simulate interaction with the judge).
  • Submitting has no rate limit, but rapid repeated submissions on the same problem are treated as score farming.