Editorial

First, compute the volume of water in the container formed by the outermost vertical lines, i.e., between the lines of the pair $(l,r)=(1,n)$. Then, move the pointers $l$ and $r$ towards each other:

• if $h_l<h_r$, increase $l$ by $1$;

• if $h_l\ge h_r$, decrease $r$ by $1$;

The volume of water between the lines $l$ and $r$ is equal to $min(h_l,h_r)\ast (r-l)$. Among all the calculated values, find the maximum.

The problem can be solved in $O(n^2)$. However, due to the constraint $n\le 10^5$, such a solution would result in a time limit exceeded (TLE). It is sufficient to iterate over the pairs of lines $(i,j)$, where $1\le i<j\le n$, and for each such pair, calculate the volume of water they can hold. Among all the computed values, find the maximum volume.

Example

The container from the first test looks like this:

The maximum amount of water can be held between the lines $2$ and $9$. The water level height is $7$, and the volume of water is $7\cdot 7=49$.

Algorithm realization

Read the input data.

scanf("%d", &n);
h.resize(n);
for (i = 0; i < n; i++)
  scanf("%lld", &h[i]);

Store the maximum amount of water the container can hold in the variable $res$.

long long res = 0;

Initialize two pointers $(l,r)=(1,n)$.

int l = 0, r = h.size() - 1;

Move the pointers $l$ and $r$ towards each other until they meet.

while (l < r)
{

The volume of water between the lines $l$ and $r$ is equal to $min(h_l,h_r)\cdot (r-l)$. Among all such volumes, find the maximum.

  res = max(res, min(h[l], h[r]) * (r - l));

Move the pointers.

  if (h[l] < h[r])
    l += 1;
  else
    r -= 1;
}

Print the answer.

printf("%lld\n", res);

Algorithm realization – O(n^2), Time Limit

Read the input data.

scanf("%d", &n);
v.resize(n);
for (i = 0; i < n; i++)
  scanf("%lld", &v[i]);

Store the maximum amount of water the container can hold in the variable $res$.

long long res = 0;

Iterate over all possible pairs of lines $(i,j)$, where $1\le i<j\le n$.

for (i = 0; i < n; i++)
for (j = i + 1; j < n; j++) 

The volume of water between the lines $l$ and $r$ is equal to $min(v_i,v_j)\cdot (j-i)$. Among all such volumes, find the maximum.

  res = max(res, min(v[i], v[j]) * (j - i));

Print the answer.

printf("%lld\n", res);