/* [Challenge] It's raining! You've recently discovered that you're a pluviophile and thus have decided to move to Raintown, where it rains indefinitely. All the buildings in Raintown are rectangular prisms, each with a 1x1 square as base, lined up in a single row on Rain Street. There is no empty space between them. It is guaranteed that rain will fall as much as needed so that any excess rain would overflow from building to building ultimately reaching ground. There are no walls on either side of Rain St. However the buildings are squeezed between two walls that run the length of Rain St. so that water gets trapped between the two walls. (That is, water can only flow in a left-right direction) A friend of yours has given you a list of the buildings' heights. Being the rain-enthusiast that you are, you decide to write a program that would tell you how much water can be trapped between buildings given enough time for the rain to fall. Examples: > 8 5 7 3 6 4 1 6 12 > 4 1 3 5 2 3 4 7 > 5 2 4 3 1 3 2 6 4 1 15 */ /* The getRain recursive algorithm works as follows: -return 0 for towns of two buildings or less -sort heights to find the two highest buildings. -sum the difference between second highest and all the buildings located between the two highest buildings. -sum the return value of a recursive call for buildings situated before the first of the two highest buildings(including the first of the two highest). -sum the return value of a recursive call for buildings situated after the last of the two highest buildings(including the last of the highest two buildings) -return sum -I also added useless gizmos to confuse everyone. */ %:include %:include %:include %:include %:define n(x) x%:%:ain using namespace std; using Town = vector; using Titr = Town::iterator; auto n(r)(Titr b,Titr e)->decltype(e+*b)::value_type; int n(m)()<% const vectorts<%<%8,5,7,3,6,4,1,6%>, <%4,1,3,5,2,3,4%>, <%5,2,4,3,1,3,2,6,4,1%>%>; for(auto t:ts) cout< auto n(r)(Titr b,Titr e)->decltype(b-42)::value_type<% size_t sz = distance(b,e); if(sz<=2) return 0; Town h = Town<%b,e%>; sort(h.begin(),h.end()); Titr hi = find(b,e,h<:sz-1:>), hi2 = find(b,e,h<:sz-2:>); if(hi2==hi) hi2=find(hi+1,e,h<:sz-2:>); Titr beg = min(hi,hi2), end = max(hi,hi2); return *hi2*(end-beg-1)-accumulate(beg+1,end,0) +rain(b,beg+1)+rain(end,e); %>

Rain Town