Drum 8

drum8

== include(page="template/taskheader" task_id="drum8") ==

Marcel are o nouă provocare pentru tine! El îţi dă doi vectori $A$ şi $B$ de lungime $N$ şi te intreabă care este drumul diagonal cu suma elementelor maximă din matricea $C$ definită astfel: $C[i][j] = A[i] * B[j]$.
 
Un drum diagonal este un drum $D$ care incepe in celula $(1, 1)$, se termina in celula $(N, N)$, efecuand numai deplasari la dreapta si in jos.

Marcel are o nouă provocare pentru tine! El îţi dă doi vectori $A$ şi $B$ de lungime $N$ şi te intreabă care este drumul cu suma elementelor maximă din matricea $C$ definită astfel: $C[i][j] = A[i] * B[j]$

h2. Date de intrare

h2. Restricţii
* $1 ≤ N ≤ 100.000$.

* $0 ≤ A[i], B[i] ≤ 2$.

* $0 ≤ A[i] ≤ 2$.

* Pentru $20$ puncte, $1 ≤ N ≤ 500$.

* Pentru alte $20$ puncte, $0 ≤ A[i], B[i] ≤ 1$.

* Pentru alte $20$ puncte, $0 ≤ A[i] ≤ 1$.

* **În cazul în care sunt mai multe drumuri care duc la suma maximă se va afişa cel minim lexicografic**.
h2. Exemplu