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

Envío 1096

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

  • Autor: svanegas
  • Fecha: 2020-10-10 18:33:56 UTC (Hace más de 3 años)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.005 s 2 KBi
#2
Correcto
0.005 s 1 KBi
#3
Correcto
0.005 s 2 KBi
#4
Correcto
0.005 s 1 KBi
#5
Correcto
0.006 s 1 KBi
#6
Correcto
0.005 s 3 KBi
#7
Correcto
0.006 s 2 KBi
#8
Correcto
0.006 s 3 KBi
#9
Correcto
0.006 s 3 KBi
#10
Correcto
0.005 s 2 KBi
#11
Correcto
0.005 s 2 KBi
#12
Correcto
0.006 s 1 KBi
#13
Correcto
0.006 s 1 KBi
#14
Correcto
0.006 s 2 KBi
#15
Correcto
0.007 s 1 KBi
#16
Correcto
0.006 s 1 KBi
#17
Correcto
0.006 s 3 KBi
#18
Correcto
0.007 s 2 KBi
Puntos totales: 100 / 100

Código

/**
* O(n^3) Algorithm to find max subrectangle sum.
* The way it works is so beautiful, it uses Kadane's algorithm.
*/
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long ll;

const ll INF = 1LL << 60;
const int MAXN = 55;

int r, c;
ll m[MAXN][MAXN], arr[MAXN];

ll
kadane() {
  ll max_sum = -INF, sum = 0;
  for (int i = 0; i < r; ++i) {
    sum += arr[i];
    if (sum < 0) sum = 0;
    else if (sum > max_sum) max_sum = sum;
  }
  if (max_sum != -INF) return max_sum;
  else {
    for (int i = 0; i < r; ++i) max_sum = max(max_sum, arr[i]);
    return max_sum;
  }
}

void
find_max_sum() {
  ll sum, max_sum = -INF;
  for (int i = 0; i < r; ++i) {
    memset(arr, 0, sizeof(arr));
    for (int j = i; j < c; ++j) {
      for (int k = 0; k < r; ++k) arr[k] += m[k][j];
      max_sum = max(max_sum, kadane());
    }
  }
  printf("%lld\n", max_sum);
}

int
main() {
  scanf("%d %d", &r, &c);
  for (int i = 0; i < r; ++i)
    for (int j = 0; j < c; ++j) scanf("%lld", &m[i][j]);
  find_max_sum();
  return 0;
}