| Fişierul intrare/ieşire: | drum8.in, drum8.out | Sursă | Algoritmiada 2022, Runda 2 |
| Autor | Alexandru Petrescu, Mihai-Cristian Popescu | Adăugată de |  Mihai-Cristian Popescu •mihai50000 |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 16384 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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.
Date de intrare
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.
Date de ieşire
Î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.
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.
Exemplu
| drum8.in | drum8.out |
|---|---|
| 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 |
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
