Разбор

Сначала вычислим объем воды в контейнере между крайними верткальными линиями, то есть между линиями пары $(l,r)=(1,n)$. Затем будем двигать указатели $l$ и $r$ навстречу друг другу:

• если $h_l<h_r$, то увеличим $l$ на $1$;

• если $h_l\ge h_r$, то уменьшим $r$ на $1$;

Объем воды между линиями $l$ и $r$ равен $min(h_l,h_r)\ast (r-l)$. Среди всех полученных значений находим наибольшее.

Задачу можно решить за $O(n^2)$. Однако из-за ограничения $n\le 10^5$ такое решение приведёт к превышению лимита времени (Time Limit). Достаточно перебрать пары линий $(i,j)$, для которых $1\le i<j\le n$, и далее для каждой такой пары вычислить объем воды, который они могут удерживать. Среди всех вычисленных значений находим максимальный объём.

Пример

Контейнер из первого теста имеет вид:

Наибольшее количество воды можно удержать между линиями $2$ и $9$. Высота уровня воды составит $7$, а объем воды равен $7\cdot 7=49$.

Реализация алгоритма

Читаем входные данные.

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

В переменной $res$ будем хранить максимальное количество воды, которое может удерживать контейнер.

long long res = 0;

Инициализируем пару указателей $(l,r)=(1,n)$.

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

Двигаем указатели $l$ и $r$ навстречу друг другу, пока они не встретятся.

while (l < r)
{

Объем воды между линиями $l$ и $r$ равен $min(h_l,h_r)\cdot (r-l)$. Среди всех таких объемов находим максимальный.

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

Перемещаем указатели.

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

Выводим ответ.

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

Реализация алгоритма — O(n^2), Time Limit

Читаем входные данные.

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

В переменной $res$ будем хранить максимальное количество воды, которое может удерживать контейнер.

long long res = 0;

Перебираем все возможные пары линий $(i,j),1\le i<j\le n$.

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

Объем воды между линиями $i$ и $j$ равен $min(v_i,v_j)\cdot (j-i)$. Среди всех таких объемов находим максимальный.

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

Выводим ответ.

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