== 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
table(example). |_. drum8.in |_. drum8.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 5
1 0 0 1 0
0 1 0 0 1
| 1 1
1 2
1 3
1 4
1 5
2 5
3 5
4 5
5 5
|
| 5
0 2 0 2 2
1 2 2 1 0
| 1 1
2 1
2 2
2 3
3 3
4 3
5 3
5 4
5 5
|
h3. Explicaţie
...
Drumul in primul exemplu:
**0** **1** **0** **0** **1**
0 0 0 0 **0**
0 0 0 0 **0**
0 1 0 0 **1**
0 0 0 0 **0**
Drumul in al doilea exemplu:
**0** 0 0 0 0
**2** **4** **4** 2 0
0 0 **0** 0 0
2 4 **4** 2 0
2 4 **4** **2** **0**
== include(page="template/taskfooter" task_id="drum8") ==
