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

Envío 1000

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 1 KBi
#5
Correcto
0.006 s 1 KBi
#6
Correcto
0.006 s 1 KBi
#7
Correcto
0.005 s 1 KBi
#8
Correcto
0.006 s 1 KBi
#9
Correcto
0.007 s 1 KBi
#10
Correcto
0.007 s 1 KBi
#11
Correcto
0.007 s 2 KBi
#12
Correcto
0.006 s 1 KBi
#13
Correcto
0.008 s 5 KBi
#14
Correcto
0.007 s 1 KBi
#15
Correcto
0.007 s 1 KBi
#16
Correcto
0.007 s 1 KBi
#17
Correcto
0.007 s 1 KBi
#18
Correcto
0.006 s 1 KBi
Puntos totales: 100 / 100

Código

#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  int R, C;
  cin >> R >> C;
  vector<vector<long>> matrix(R, vector<long>(C));
  long max_sum = INT_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]);
    }
  }
  if (max_sum <= 0) {
    cout << max_sum << endl;
    return 0;
  }

  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 col = 0; col < C; col++) {
    vector<long> sums(R);
    for (int j = col; j < C; j++) {
      long gmax = INT_MIN;
      long currMax = gmax;
      for (int i = 0; i < R; ++i) {
        long sum = matrix[i][j];

        if (col > 0) {
          sum -= matrix[i][col - 1];
        }
        currMax = max(sum, sum + currMax);
        gmax = max(gmax, currMax);
      }
      max_sum = max(max_sum, gmax);
    }
  }
  cout << max_sum << endl;
}