█████████ ████ ███░░░░░███ ░░███ ███ ░░░ ██████ ███████ ██████ ██████ ░███ ███░░███ ███░░███ ███░░███ ███░░███ ░███ ░███ ░███░███ ░███ ░███████ ░███ ░███ ░░███ ███░███ ░███░███ ░███ ░███░░░ ░███ ░███ ░░█████████ ░░██████ ░░████████░░██████ ░░██████ ░░░░░░░░░ ░░░░░░ ░░░░░░░░ ░░░░░░ ░░░░░░

Envío 5156

Problema 0xa6 - Submatriz de suma máxima en una matriz no muy grande

  • Autor: jarangolp
  • Fecha: 2021-10-20 05:23:49 UTC (Hace alrededor de 3 años)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.007 s 13 KBi
#2
Correcto
0.006 s 0 KBi
#3
Correcto
0.004 s 8 KBi
#4
Correcto
0.005 s 0 KBi
#5
Correcto
0.005 s 0 KBi
#6
Correcto
0.004 s 12 KBi
#7
Correcto
0.004 s 0 KBi
#8
Tiempo límite excedido
1.058 s 0 KBi
#9
Tiempo límite excedido
1.1 s 0 KBi
#10
Tiempo límite excedido
1.006 s 0 KBi
#11
Tiempo límite excedido
1.062 s 24 KBi
#12
Tiempo límite excedido
1.017 s 1 KBi
#13
Tiempo límite excedido
1.083 s 19 KBi
#14
Tiempo límite excedido
1.062 s 5 KBi
#15
Tiempo límite excedido
1.088 s 0 KBi
#16
Tiempo límite excedido
1.086 s 12 KBi
#17
Tiempo límite excedido
1.052 s 0 KBi
#18
Tiempo límite excedido
1.088 s 7 KBi
Puntos totales: 39 / 100

Código

#include <iostream>

using namespace std;


int main() {
  int R, C;
  cin >> R >> C;
  int matrix[R][C];
  for (int i = 0; i < R; i++) {
    for (int j = 0; j < C; j++) {
      cin >> matrix[i][j];
    }
  }

  int max = matrix[0][0];
  for (int r0 = 0; r0 < R; r0++) {
    for (int c0 = 0; c0 < C; c0++) {
      for (int r1 = r0; r1 < R; r1++) {
        for (int c1 = c0; c1 < C; c1++) {
          int sum = 0;
          for (int r = r0; r <= r1; r++) {
            for (int c = c0; c <= c1; c++ ) {
              sum += matrix[r][c];
            }
          }
          if (sum > max)
            max = sum;
        }
      }
    }
  }
  cout << max << endl;
  return 0;
}