maxsubsum

MaxSubSum

== 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") ==