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

Envío 987

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

Caso # Resultado Tiempo Memoria
#1
Correcto
0.005 s 1 KBi
#2
Correcto
0.005 s 1 KBi
#3
Correcto
0.005 s 1 KBi
#4
Correcto
0.005 s 8 KBi
#5
Correcto
0.005 s 1 KBi
#6
Correcto
0.004 s 1 KBi
#7
Incorrecto
0.005 s 1 KBi
#8
Incorrecto
0.038 s 1 KBi
#9
Correcto
0.038 s 20 KBi
#10
Correcto
0.041 s 1 KBi
#11
Correcto
0.04 s 28 KBi
#12
Incorrecto
0.033 s 1 KBi
#13
Incorrecto
0.039 s 1 KBi
#14
Incorrecto
0.041 s 1 KBi
#15
Correcto
0.041 s 1 KBi
#16
Incorrecto
0.037 s 2 KBi
#17
Correcto
0.042 s 1 KBi
#18
Correcto
0.033 s 1 KBi
Puntos totales: 67 / 100

Código

#include <algorithm>
#include <bits/stdc++.h>
using namespace std;

long sum_of(vector<vector<long>> &matrix, int i, int r, int j, int c) {
    long total = matrix[r][c];
    if (i > 0) {
        total -= matrix[i-1][c];
    }
    if (j > 0) {
        total -= matrix[r][j-1];
    }
    return total;
}

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

  for (int i = 1; i < R; i++) {
    for (int j = 0; j < C; j++) {
      matrix[i][j] += matrix[i - 1][j];
      max_sum = max(max_sum, matrix[i][j]);
    }
  }

  for (int i = 0; i < R; i++) {
    for (int j = 1; j < C; j++) {
      matrix[i][j] += matrix[i][j - 1];
      max_sum = max(max_sum, matrix[i][j]);
    }
  }

  for (int i = 0; i < R; i++) {
    for (int j = 0; j < C; j++) {
      for (int r = i + 1; r < R; r++) {
        for (int c = j + 1; c < C; c++) {
          max_sum = max(max_sum, sum_of(matrix, i, r, j, c));
        }
      }
    }
  }
  cout << max_sum << endl;
}