Vectores Segmentables X95177

Dados un vector $A$ de números naturales y una constante $k > 0$, una $k$-segmentación del vector se construye de la siguiente forma: Se comienza desde el primer elemento y se van sumando elementos mientras la suma sea menor o igual que $k$. A continuación se empiezan a restar elementos mientras la suma sea mayor o igual que $0$. A continuación se comienzan a sumar elementos mientras la suma sea menor o igual que $k$ y así sucesivamente. El vector es $k$-segmentable si con este proceso se llega al final del vector.

Por ejemplo, el vector $A = \{4, 4, 1, 2, 6, 7, 1, 1, 8, 2, 6, 7\}$ es $9$-segmentable porque se puede atravesar todo el vector siguiendo el procedimiento descrito anteriormente como se ve a continuación (donde $S$ es la suma):

A: 4 4 1 2 6 7 1 1 8 2 6 7
S: 4 8 9 7 1 8 9 8 0 2 8 1
   + + + - - + + - - + + -

En cambio, el vector no es $8$-segmentable porque si tomamos $k = 8$, nos quedamos parados a medio camino, ya que el 6 no podemos ni sumarlo ni restarlo sin superar $k$ o ser negativo:

A: 4 4 1 2 6 7 1 1 8 2 6 7
S: 4 8 7 5
   + + - -

Escriba un programa que encuentre la $k$ más pequeña tal que $A$ sea $k$-segmentable. Se puede demostrar que siempre existe un valor de $k$ tal que $k \le 2\cdot\max\{A[i]\}, 0\le y < A.size()$.

Entrada

La entrada consiste en un natural $n$, seguido de $n$ naturales A[0], …, A[n-1].

Salida

La salida es el mínimo valor de $k$ tal que A es $k$-segmentable.

Observación

Se recomienda utilizar una función:

bool es_segmentable(const vector<int>& A, int k)

 
que determina si el vector es $k$-segmentable.

Para diseñar una solución eficiente, conviene pensar en todos aquellos valores de $k$ que no hace falta probar.