Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | maxsubsum.in, maxsubsum.out | Sursă | ONIS 2016 Runda Online |
| Autor | Mihai Calancea | Adăugată de |  Adrian Budau •freak93 |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | maxsubsum.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.
