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

Envío 980

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

  • Autor: davidtoca
  • Fecha: 2020-10-05 16:30:52 UTC (Hace más de 3 años)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.005 s 1 KBi
#2
Correcto
0.005 s 1 KBi
#3
Correcto
0.007 s 6 KBi
#4
Correcto
0.005 s 1 KBi
#5
Correcto
0.006 s 1 KBi
#6
Correcto
0.006 s 1 KBi
#7
Correcto
0.005 s 4 KBi
#8
Tiempo límite excedido
0.583 s 2 KBi
#9
Tiempo límite excedido
0.162 s 1 KBi
#10
Tiempo límite excedido
0.334 s 1 KBi
#11
Tiempo límite excedido
0.184 s 1 KBi
#12
Tiempo límite excedido
0.188 s 5 KBi
#13
Tiempo límite excedido
0.188 s 1 KBi
#14
Tiempo límite excedido
0.174 s 1 KBi
#15
Tiempo límite excedido
0.206 s 1 KBi
#16
Tiempo límite excedido
0.2 s 1 KBi
#17
Tiempo límite excedido
0.232 s 1 KBi
#18
Tiempo límite excedido
0.183 s 1 KBi
Puntos totales: 39 / 100

Código

#include <iostream>
#include <algorithm>

using namespace std;

int sum(int x1, int y1, int x2, int y2, int matrix[50][50]){
  int total;

  for(int col=y1; col<=y2;col++){
    for(int row=x1; row<=x2;row++){
      total+=matrix[row][col];
    }
  }

  return total;
}

int main() {
  int r,c;
  cin >>r >> c;

  int matrix[r][c];

  for(int row=0;row<r; row++){
    for(int col=0;col<c; col++){
      cin >> matrix[row][col];
    }

  }
  int x1,y1, x2,y2, response=-100001, total;

  for(int row=0;row<r; row++){
    for(int col=0;col<c; col++){
      x1=row;
      y1=col;

      x2=x1;
      y2=y1;

      for(int col2=y1;col2<c; col2++){
        for(int row2=x1;row2<r; row2++){
          
          y2=col2;
          x2=row2;

          //total = sum(x1,y1,x2,y2,matrix);
          total = 0;

            for(int col3=y1; col3<=y2;col3++){
              for(int row3=x1; row3<=x2;row3++){
                total+=matrix[row3][col3];
              }
            }
        

          response = max(response, total);
          //cout <<response << endl;

      }
      }
    }
  }

  cout << response << endl;

}