Hola, les traigo un problema de una competencia de hoy que me pareció copado.
Enunciado
Se tiene una barra de chocolate rectangular dividida en cuadraditos por H filas y W columnas.
El cuadradito (i,j), situado en la fila i y la columna j, es de chocolate oscuro si S_{ij} es 0 y es de chocolate blanco si S_{ij} es 1.
Podemos cortar el chocolate para dividirlo a lo largo de una columna o a lo largo de una fila. Cada corte se realiza a lo largo de toda una fila o toda una columna de la barra completa, de punta a punta.
¿Cuál es la mínima cantidad de cortes que se deben realizar para que al finalizar los cortes cada bloque tenga K o menos cuadraditos de chocolate blanco?
Cotas
- 1 \leq H \leq 10
- 1 \leq W \leq 1000
- 1 \leq K \leq H \times W
- S_{ij} \in \{0,1\}
Aclaración
Envío
Creándose un usuario, pueden realizar sus envíos acá. Si no, pueden contar la idea de su solución y la discutimos.