Envío 998

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

Autor: alvaro.ardila@gmail.com
Fecha: 2020-10-06 17:39:43 UTC (Hace alrededor de 4 años)

Caso #	Resultado	Tiempo	Memoria
#1	Error de compilación Compilation time limit exceeded.
#2	Correcto	0.006 s	1 KBi
#3	Error de compilación Compilation time limit exceeded.
#4	Error de compilación Compilation time limit exceeded.
#5	Correcto	0.005 s	3 KBi
#6	Error de compilación Compilation time limit exceeded.
#7	Correcto	0.005 s	1 KBi
#8	Error de compilación Compilation time limit exceeded.
#9	Correcto	0.007 s	20 KBi
#10	Correcto	0.009 s	1 KBi
#11	Error de compilación Compilation time limit exceeded.
#12	Correcto	0.008 s	1 KBi
#13	Correcto	0.009 s	8 KBi
#14	Error de compilación Compilation time limit exceeded.
#15	Error de compilación Compilation time limit exceeded.
#16	Error de compilación Compilation time limit exceeded.
#17	Error de compilación Compilation time limit exceeded.
#18	Error de compilación Compilation time limit exceeded.

Puntos totales: 39 / 100

Código

#include <algorithm>
#include <bits/stdc++.h>
#include <climits>
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]);
    }
  }

  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++) {
      for (int i = 0; i < R; i++) {
        sums[i] = matrix[i][j];
        if (col > 0) {
          sums[i] -= matrix[i][col - 1];
        }
      }
      long gmax = sums[0];
      long currMax = gmax;
      for (int i = 1; i < sums.size(); ++i) {
        currMax = max(sums[i], sums[i] + currMax);
        gmax = max(gmax, currMax);
      }
      max_sum = max(max_sum, gmax);
    }
  }
  cout << max_sum << endl;
}