There is a cup, which can be considered as having a volume composed of two rectangular prisms (as shown in the figure below). The base area of the lower rectangular prism is w1 × w1 cm square, with a height of h1 cm. The base area of the upper rectangular prism is w2×w2 cm2, with a height of h2 cm.
Initially, the cup is empty. You need to pour a drink into the cup \( n \) times, with each pour having a volume of \( v \) cm3. Once the cup is full, the water level will no longer rise. What is the maximum change in water level in centimeters during these \( n \) pours?
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The first line contains a positive integer N (1 ≤ N ≤ 10), representing the number of times the drink needs to be poured. The next line contains four positive integers w1, w2, h1, and h2 (1 ≤ w1, w2, h1, h2 ≤ 50), representing the width and height of the cup. The last line contains N positive integers representing the volume of the drink poured each time. It is guaranteed that the water level rise is an integer each time. | Output the maximum height change in the water level during these N pours. |
| 1 4 6 8 5 200 | 10 |
| 2 5 10 12 8 400 600 | 13 |
| 5 16 44 28 17 2560 1280 1536 1024 10448 | 10 |
Thought Process
Use the prefix sum method to determine how much the water level will rise from the bottom with each pour. Then, subtract the previous water level rise to find the height increase for the current pour.
Sample Code－ZeroJudge O711: Packing Drinks
#include <iostream>
using namespace std;
int N, w1, w2, h1, h2;
int first, second;
int calcLevel(const int w) {
int level;
if (w <= first) {
level = w / (w1*w1);
}
else if (w <= first + second) {
level = h1 + ((w-first) / (w2*w2));
}
else {
level = h1 + h2;
}
return level;
}
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
cin >> N >> w1 >> w2 >> h1 >> h2;
first = w1 * w1 * h1;
second = w2 * w2 * h2;
int water[20] = {}, prefix[20] = {}, calc[20] = {}, ans = -999;
prefix[0] = 0;
calc[0] = 0;
for (int i = 0; i<N; i++) {
cin >> water[i];
prefix[i+1] = prefix[i] + water[i];
}
for (int i = 0; i<N; i++) {
const int level = calcLevel(prefix[i+1]);
calc[i+1] = level;
ans = max(ans, level-calc[i]);
}
cout << ans << "\n";
}
//ZeroJudge O711
//Dr. SeanXD