drum8

Drum 8

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

Poveste şi cerinţă...

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.

h2. Date de intrare

Fişierul de intrare $drum8.in$ ...

Fişierul de intrare $drum8.in$ conţine, pe prima linie numărul $N$, dimensiunea vectorilor $A$ şi $B$. Urmează două linii, fiecare având câte $N$ numere. Prima linie conţine elementele vectorului $A$, iar cea de-a doua elementele vectorului $B$.

h2. Date de ieşire

În fişierul de ieşire $drum8.out$ ...

În fişierul de ieşire $drum8.out$ se vor afişa poziţiile din drumul de suma maxima, în ordinea în care acestea sunt vizitate, fiecare pe câte o linie.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100.000$.
* $0 ≤ A[i], B[i] ≤ 2$.
* Pentru $20$ puncte, $1 ≤ N ≤ 500$.
* Pentru alte $20$ puncte, $0 ≤ A[i], B[i] ≤ 1$.
* **În cazul în care sunt mai multe drumuri care duc la suma maximă se va afişa cel minim lexicografic**.

h2. Exemplu

h3. Explicaţie

Matricea pentru primul exemplu este:

Drumul in primul exemplu:

**0** **1** **0** **0** **1**
0 0 0 0 **0**

0 1 0 0 **1**
0 0 0 0 **0**

Matricea pentru al doilea exemplu este:

Drumul in al doilea exemplu:

**0** 0 0 0 0
**2** **4** **4** 2 0