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

Envío 1095

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

  • Autor: svanegas
  • Fecha: 2020-10-10 18:33:17 UTC (Hace alrededor de 4 años)
Caso # Resultado Tiempo Memoria
#1
Error de compilación 
                      main.cpp:36:5: error: use of undeclared identifier 'memset'; did you mean 'wmemset'?
    memset(arr, 0, sizeof(arr));
    ^~~~~~
    wmemset
/usr/include/wchar.h:271:17: note: 'wmemset' declared here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                ^
main.cpp:36:12: error: cannot initialize a parameter of type 'wchar_t *' with an lvalue of type 'll [55]'
    memset(arr, 0, sizeof(arr));
           ^~~
/usr/include/wchar.h:271:35: note: passing argument to parameter '__s' here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                                  ^
2 errors generated.
#2
Error de compilación 
                      main.cpp:36:5: error: use of undeclared identifier 'memset'; did you mean 'wmemset'?
    memset(arr, 0, sizeof(arr));
    ^~~~~~
    wmemset
/usr/include/wchar.h:271:17: note: 'wmemset' declared here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                ^
main.cpp:36:12: error: cannot initialize a parameter of type 'wchar_t *' with an lvalue of type 'll [55]'
    memset(arr, 0, sizeof(arr));
           ^~~
/usr/include/wchar.h:271:35: note: passing argument to parameter '__s' here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                                  ^
2 errors generated.
#3
Error de compilación 
                      main.cpp:36:5: error: use of undeclared identifier 'memset'; did you mean 'wmemset'?
    memset(arr, 0, sizeof(arr));
    ^~~~~~
    wmemset
/usr/include/wchar.h:271:17: note: 'wmemset' declared here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                ^
main.cpp:36:12: error: cannot initialize a parameter of type 'wchar_t *' with an lvalue of type 'll [55]'
    memset(arr, 0, sizeof(arr));
           ^~~
/usr/include/wchar.h:271:35: note: passing argument to parameter '__s' here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                                  ^
2 errors generated.
#4
Error de compilación 
                      main.cpp:36:5: error: use of undeclared identifier 'memset'; did you mean 'wmemset'?
    memset(arr, 0, sizeof(arr));
    ^~~~~~
    wmemset
/usr/include/wchar.h:271:17: note: 'wmemset' declared here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                ^
main.cpp:36:12: error: cannot initialize a parameter of type 'wchar_t *' with an lvalue of type 'll [55]'
    memset(arr, 0, sizeof(arr));
           ^~~
/usr/include/wchar.h:271:35: note: passing argument to parameter '__s' here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                                  ^
2 errors generated.
#5
Error de compilación 
                      main.cpp:36:5: error: use of undeclared identifier 'memset'; did you mean 'wmemset'?
    memset(arr, 0, sizeof(arr));
    ^~~~~~
    wmemset
/usr/include/wchar.h:271:17: note: 'wmemset' declared here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                ^
main.cpp:36:12: error: cannot initialize a parameter of type 'wchar_t *' with an lvalue of type 'll [55]'
    memset(arr, 0, sizeof(arr));
           ^~~
/usr/include/wchar.h:271:35: note: passing argument to parameter '__s' here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                                  ^
2 errors generated.
#6
Error de compilación 
                      main.cpp:36:5: error: use of undeclared identifier 'memset'; did you mean 'wmemset'?
    memset(arr, 0, sizeof(arr));
    ^~~~~~
    wmemset
/usr/include/wchar.h:271:17: note: 'wmemset' declared here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                ^
main.cpp:36:12: error: cannot initialize a parameter of type 'wchar_t *' with an lvalue of type 'll [55]'
    memset(arr, 0, sizeof(arr));
           ^~~
/usr/include/wchar.h:271:35: note: passing argument to parameter '__s' here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                                  ^
2 errors generated.
#7
Error de compilación 
                      main.cpp:36:5: error: use of undeclared identifier 'memset'; did you mean 'wmemset'?
    memset(arr, 0, sizeof(arr));
    ^~~~~~
    wmemset
/usr/include/wchar.h:271:17: note: 'wmemset' declared here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                ^
main.cpp:36:12: error: cannot initialize a parameter of type 'wchar_t *' with an lvalue of type 'll [55]'
    memset(arr, 0, sizeof(arr));
           ^~~
/usr/include/wchar.h:271:35: note: passing argument to parameter '__s' here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                                  ^
2 errors generated.
#8
Error de compilación 
                      main.cpp:36:5: error: use of undeclared identifier 'memset'; did you mean 'wmemset'?
    memset(arr, 0, sizeof(arr));
    ^~~~~~
    wmemset
/usr/include/wchar.h:271:17: note: 'wmemset' declared here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                ^
main.cpp:36:12: error: cannot initialize a parameter of type 'wchar_t *' with an lvalue of type 'll [55]'
    memset(arr, 0, sizeof(arr));
           ^~~
/usr/include/wchar.h:271:35: note: passing argument to parameter '__s' here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                                  ^
2 errors generated.
#9
Error de compilación 
                      main.cpp:36:5: error: use of undeclared identifier 'memset'; did you mean 'wmemset'?
    memset(arr, 0, sizeof(arr));
    ^~~~~~
    wmemset
/usr/include/wchar.h:271:17: note: 'wmemset' declared here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                ^
main.cpp:36:12: error: cannot initialize a parameter of type 'wchar_t *' with an lvalue of type 'll [55]'
    memset(arr, 0, sizeof(arr));
           ^~~
/usr/include/wchar.h:271:35: note: passing argument to parameter '__s' here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                                  ^
2 errors generated.
#10
Error de compilación 
                      main.cpp:36:5: error: use of undeclared identifier 'memset'; did you mean 'wmemset'?
    memset(arr, 0, sizeof(arr));
    ^~~~~~
    wmemset
/usr/include/wchar.h:271:17: note: 'wmemset' declared here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                ^
main.cpp:36:12: error: cannot initialize a parameter of type 'wchar_t *' with an lvalue of type 'll [55]'
    memset(arr, 0, sizeof(arr));
           ^~~
/usr/include/wchar.h:271:35: note: passing argument to parameter '__s' here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                                  ^
2 errors generated.
#11
Error de compilación 
                      main.cpp:36:5: error: use of undeclared identifier 'memset'; did you mean 'wmemset'?
    memset(arr, 0, sizeof(arr));
    ^~~~~~
    wmemset
/usr/include/wchar.h:271:17: note: 'wmemset' declared here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                ^
main.cpp:36:12: error: cannot initialize a parameter of type 'wchar_t *' with an lvalue of type 'll [55]'
    memset(arr, 0, sizeof(arr));
           ^~~
/usr/include/wchar.h:271:35: note: passing argument to parameter '__s' here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                                  ^
2 errors generated.
#12
Error de compilación 
                      main.cpp:36:5: error: use of undeclared identifier 'memset'; did you mean 'wmemset'?
    memset(arr, 0, sizeof(arr));
    ^~~~~~
    wmemset
/usr/include/wchar.h:271:17: note: 'wmemset' declared here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                ^
main.cpp:36:12: error: cannot initialize a parameter of type 'wchar_t *' with an lvalue of type 'll [55]'
    memset(arr, 0, sizeof(arr));
           ^~~
/usr/include/wchar.h:271:35: note: passing argument to parameter '__s' here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                                  ^
2 errors generated.
#13
Error de compilación 
                      main.cpp:36:5: error: use of undeclared identifier 'memset'; did you mean 'wmemset'?
    memset(arr, 0, sizeof(arr));
    ^~~~~~
    wmemset
/usr/include/wchar.h:271:17: note: 'wmemset' declared here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                ^
main.cpp:36:12: error: cannot initialize a parameter of type 'wchar_t *' with an lvalue of type 'll [55]'
    memset(arr, 0, sizeof(arr));
           ^~~
/usr/include/wchar.h:271:35: note: passing argument to parameter '__s' here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                                  ^
2 errors generated.
#14
Error de compilación 
                      main.cpp:36:5: error: use of undeclared identifier 'memset'; did you mean 'wmemset'?
    memset(arr, 0, sizeof(arr));
    ^~~~~~
    wmemset
/usr/include/wchar.h:271:17: note: 'wmemset' declared here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                ^
main.cpp:36:12: error: cannot initialize a parameter of type 'wchar_t *' with an lvalue of type 'll [55]'
    memset(arr, 0, sizeof(arr));
           ^~~
/usr/include/wchar.h:271:35: note: passing argument to parameter '__s' here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                                  ^
2 errors generated.
#15
Error de compilación 
                      main.cpp:36:5: error: use of undeclared identifier 'memset'; did you mean 'wmemset'?
    memset(arr, 0, sizeof(arr));
    ^~~~~~
    wmemset
/usr/include/wchar.h:271:17: note: 'wmemset' declared here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                ^
main.cpp:36:12: error: cannot initialize a parameter of type 'wchar_t *' with an lvalue of type 'll [55]'
    memset(arr, 0, sizeof(arr));
           ^~~
/usr/include/wchar.h:271:35: note: passing argument to parameter '__s' here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                                  ^
2 errors generated.
#16
Error de compilación 
                      main.cpp:36:5: error: use of undeclared identifier 'memset'; did you mean 'wmemset'?
    memset(arr, 0, sizeof(arr));
    ^~~~~~
    wmemset
/usr/include/wchar.h:271:17: note: 'wmemset' declared here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                ^
main.cpp:36:12: error: cannot initialize a parameter of type 'wchar_t *' with an lvalue of type 'll [55]'
    memset(arr, 0, sizeof(arr));
           ^~~
/usr/include/wchar.h:271:35: note: passing argument to parameter '__s' here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                                  ^
2 errors generated.
#17
Error de compilación 
                      main.cpp:36:5: error: use of undeclared identifier 'memset'; did you mean 'wmemset'?
    memset(arr, 0, sizeof(arr));
    ^~~~~~
    wmemset
/usr/include/wchar.h:271:17: note: 'wmemset' declared here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                ^
main.cpp:36:12: error: cannot initialize a parameter of type 'wchar_t *' with an lvalue of type 'll [55]'
    memset(arr, 0, sizeof(arr));
           ^~~
/usr/include/wchar.h:271:35: note: passing argument to parameter '__s' here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                                  ^
2 errors generated.
#18
Error de compilación 
                      main.cpp:36:5: error: use of undeclared identifier 'memset'; did you mean 'wmemset'?
    memset(arr, 0, sizeof(arr));
    ^~~~~~
    wmemset
/usr/include/wchar.h:271:17: note: 'wmemset' declared here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                ^
main.cpp:36:12: error: cannot initialize a parameter of type 'wchar_t *' with an lvalue of type 'll [55]'
    memset(arr, 0, sizeof(arr));
           ^~~
/usr/include/wchar.h:271:35: note: passing argument to parameter '__s' here
extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) __THROW;
                                  ^
2 errors generated.
Puntos totales: 0 / 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>

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;
}