Prologin, le concours national d'informatique

Énoncé¶

Joseph est à deux pas de la forteresse ! Il ne reste plus qu'un pont à passer et il pourra enfin atteindre l'entrée. Malheureusement, certaines parties du pont menacent de s'effondrer car il est très vieux. Le scaphandre de Joseph est très lourd et cet objet le fatigue. Il veut éviter de s'épuiser afin d'arriver en bon état à la forteresse.

Le pont est un passage de $N$ mètres de long, qui alterne entre zones sûres et zones fragiles. On vous décrit le pont à l'aide d'un tableau de 0 et de 1 : un chiffre tous les mètres, un 0 décrit une position dans une zone sûre, un 1 décrit une position dans une zone fragile. Une zone sûre est donc représentée par un ou plusieurs 0 consécutifs, et une zone fragile par un ou plusieurs 1 consécutifs.

Lors de sa traversée, à chaque mètre, Joseph Nageant peut soit se déplacer en marchant, soit en nageant. Joseph Nageant doit traverser le tunnel en nageant dans toutes les zones fragiles, pour éviter de faire s'écrouler le pont. Dans les zones sûres, il peut soit passer en nageant, soit en marchant.

Contrairement à l'exercice Passage Tout Juste, Joseph n'est pas obligé de marcher dans chaque zone sûre. Il peut cette fois-ci traverser une zone sûre dans son intégralité en nageant. En revanche, Joseph est obligé de marcher au moins une fois durant son parcours.

Cependant, Joseph dispose d'une certaine endurance $E \geq 0$ qui lui permet de nager pendant au maximum $E$ mètres avant de devoir se remettre à marcher. Après avoir nagé, il est obligé de marcher pendant au minimum $R$ mètres avant d'entamer sa prochaine nage ou la fin du pont. (Joseph ne peut donc pas commencer une phase de marche pendant les $R-1$ derniers mètres. Par ailleurs, si Joseph commence par une phase de marche, il doit quand même marcher pendant au moins $R$ mètres avant de commencer à nager.)

On appelle la force de Joseph la valeur de $R$ - $E$. Aidez Joseph Nageant à trouver une stratégie de déplacement qui maximise sa force.

Entrée¶

L’entrée contiendra :

Sur la première ligne, un entier : N, la longueur (en mètres) du pont.
Sur la ligne suivante, une liste de N entiers séparés par des espaces : pont, le tableau représentant les zones sûres et les zones fragiles du pont. Un chiffre par mètre : Un 0 correspond à une position dans une zone sûre, et un 1 correspond à une position dans une zone fragile.

Sortie¶

Afficher la valeur de force maximale que Joseph Nageant peut obtenir en traversant le pont.

Contraintes¶

$1 \le N \le 1\,000$
$\mathtt{pont}_i \in {0, 1}$
Il y a toujours au moins une zone de repos

Contraintes de performance¶

$1 \le N \le 500\,000$

Contraintes d'exécution

Utilisation mémoire maximum: 100000 kilo-octets
Temps d'exécution maximum: 500 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée

9
1 0 1 0 0 0 1 1 1

Exemple de sortie

Commentaire

Joseph Nageant est ici confronté à un pont d'une longueur de 9 mètres. Pour maximiser sa force, Joseph peut considérer une valeur d'endurance $E = 3$, et une valeur de repos $R = 3$.

parcours

Son parcours ressemblerait alors à : - D'abord, il nage par-dessus les deux premières zones fragiles sur trois mètres ($3 \leq E$); - Il effectue les trois mètres suivants, dans la seconde zone sûre, en marchant ($3 \geq R$); - Et finalement, il effectue les trois derniers mètres en nageant pour passer la dernière zone fragile ($3 \leq E$).

Cet exemple de parcours attribue à Joseph une force de $R - E = 3 - 3 = 0$. Il n'est pas possible de traverser le pont avec une plus grande force.