Water Held between Thin Walls
National Olympiad — Regional round (2020 season)
Submission name: dry.cpp
Problem summary
Thin walls at equal spacings divide a channel into gaps. Water overflows shorter internal walls and escapes at the ends. Find retained volume.
Input
n u v and n heights; u is spacing and v channel width.
Output
Retained volume.
Constraints
2 ≤ n ≤ 100; 1 ≤ u,v ≤ 5; heights 1…12.
Worked example
Input and output for the worked example discussed below.
Input
5 1 1 2 4 8 5 7
Output
20
Solution analysis
- The gap after wall i is bounded by the highest wall to its left and the highest wall to its right. Its water level is the minimum of these maxima.
- Precompute suffix maxima and scan while maintaining the left maximum. Each gap contributes level×u×v; walls are negligibly thin, so their heights are not subtracted from gap volume.
- For [2,4,8,5,7], the levels are 2,4,7,7, giving 20 for unit footprints. Adjacent-wall minima alone would miss water above short internal walls.
Why it works
The smaller of the highest barriers on both sides is the highest level that cannot escape.
Complexity: O(n) time and O(n) space.
Watch out. Do not use the thick-bar formula that subtracts a wall height from each gap.
Commented C++17 solution
An independently written complete program with standard headers.
// The smaller of the highest barriers on both sides is the highest level that cannot escape.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
int count,gap,width;
cin>>count>>gap>>width;
vector<int>height(count),suffix(count);
for(int&value:height){
cin>>value;
}
suffix.back()=height.back();
for(int index=count-2;index>=0;index--){
suffix[index]=max(height[index],suffix[index+1]);
}
int left=0;
int answer=0;
for(int index=0;index+1<count;index++){
left=max(left,height[index]);
answer+=min(left,suffix[index+1])*gap*width;
}
cout<<answer<<'\n';
}