Fişierul intrare/ieşire:maxsubsum.in, maxsubsum.outSursăONIS 2016 Runda Online
AutorMihai CalanceaAdăugată defreak93Adrian Budau freak93
Timp execuţie pe test0.15 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

MaxSubSum

Fie două siruri A si B cu numere întregi, de lungime N, respectiv M. Definim matricea C cu Ci,j = Ai + Bj.

Vi se cere sa gasiti submatricea de suma maxima din C. Mai exact vi se cere suma maxima S care se poate obtine adunand Ci,j cu r1 ≤ i ≤ r2, c1 ≤ j ≤ c2 cu r1, r2, c1, c2 alesi convenabil.

Date de intrare

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.

Date de ieşire

În fişierul de ieşire maxsubsum.out trebuie sa se afle un singur numar, submatricea de suma maxima din C.

Restricţii

  • 1 ≤ N,M ≤ 2.000
  • -1.000.000.000 ≤ Ai, Bj ≤ 1.000.000.000
  • Se poate alege si o submatrice formata din 0 elemente, suma obtinuta fiind 0 astfel

Exemplu

maxsubsum.inmaxsubsum.out
4 4
1 1 7 -9
-7 5 0 2
48

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?