Cuadrado Máximo

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 64M

Author:

wizard98

Problem types

Allowed languages

Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

Los Cibernéticos están implementando un nueva forma de cultivo de papa. En vez de sembrarlas en surcos, como es costumbre, las están sembrando en parcelas cuadradas de un metro de lado. El campo contiene $NxN$ $N x N$ $(3 \le N \le 300)$ $(3 \leq N \leq 300)$ de estas parcelas. De cada parcela se sabe la cantidad de papas que dará al hacer la cosecha. Esta cantidad puede ser negativa porque si las papas están podridas pueden podrir otras. Después de tanto pensar, los Cibernéticos se dieron cuenta que, dada esta forma de cultivo, la mejor manera de cosechar el campo es con un tractor especial, con sistema progamado en Java, que solo recoge un área cuadrada del campo. Calcule la mayor recolección posible utilizando el tractor solo una vez.

Entrada

Línea $1$ $1$ : Un entero positivo $N$ $N$ .

Líneas $2..N+1$ $2. . N + 1$ : Cada línea contiene $N$ $N$ enteros en el rango $[-100, 100]$ $[- 100, 100]$ .

Salida

Escribir la mayor cantidad de papas que se pueden recoger utilizando el tractor solo una vez.

Ejemplo de Entrada 1

Copy

Ejemplo de Salida 1

Copy

Ejemplo de Entrada 2

Copy

Ejemplo de Salida 2

Copy

Comments

0

Primervirgen commented on Aug. 18, 2019, 4:14 p.m.

Por que estructura de datos puedo resolver este problema?

6

aniervs commented on Aug. 19, 2019, 11:03 a.m.

Haces una tabla acumulativa en 2D, luego iteras por el tamaño del lado de los cuadrados, y cuando estás en un tamaño T, iteras por los cuadrados de T x T, computas la suma de cada uno usando la tabla acumulativa y vas guardando el máximo. Si la matriz es de N x N, computar la tabla acumulativa toma tiempo O(N^2), hay N posibles tamaños posibles del lado de los cuadrados, y para cada tamaño, hay O(N^2) cuadrados, por tanto haces O(N^3) operaciones, que es suficiente para este problema.