== include(page="template/taskheader" task_id="maxsubsum") ==
Poveste şi cerinţă...
Fie $două$ siruri $A$ si $B$ cu numere întregi, de lungime $N$, respectiv $M$. Definim matricea $C$ cu $C{~i,j~} = A{~i~} + B{~j~}$.
Vi se cere sa gasiti submatricea de suma maxima din $C$. Mai exact vi se cere suma maxima $S$ care se poate obtine adunand $C{~i,j~}$ cu $r1 ≤ i ≤ r2$, $c1 ≤ j ≤ c2$ cu $r1, r2, c1, c2$ alesi convenabil.
h2. Date de intrare
Fişierul de intrare $maxsubsum.in$ ...
Fişierul de intrare $maxsubsum.in$ va contine pe prima linie $2$ numere intregi separate prin spatiu $N$ si $M$.
Urmatorul rand va contine $N$ numere separate prin spatiu, elementele sirului $A$.
Cel de-al treilea rand va contine $M$ numere separate prin spatiu, elementele sirului $B$.
h2. Date de ieşire
În fişierul de ieşire $maxsubsum.out$ ...
În fişierul de ieşire $maxsubsum.out$ trebuie sa se afle un singur numar, submatricea de suma maxima din $C$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N,M ≤ 2.000$
* $-1.000.000.000 ≤ A{~i~}, B{~j~} ≤ 1.000.000.000$
* $Se poate alege si o submatrice formata din 0 elemente, suma obtinuta fiind 0 astfel$
h2. Exemplu
table(example). |_. maxsubsum.in |_. maxsubsum.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4 4
1 1 7 -9
-7 5 0 2
| 48
|
h3. Explicaţie
...
Matricea $C$ arata in felul urmator
-6 *6* *1* *3*
-6 *6* *1* *3*
0 *12* *7* *9*
-16 -4 -9 -7.
Se alege submatricea de $3 pe 3$ ingrosata.
== include(page="template/taskfooter" task_id="maxsubsum") ==
