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

Envío 2050

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

  • Autor: S8Vega
  • Fecha: 2020-11-20 04:08:44 UTC (Hace alrededor de 4 años)
Caso # Resultado Tiempo Memoria
#1
Correcto 
                      main.cpp:56:9: warning: 'dbg' macro redefined [-Wmacro-redefined]
#define dbg(...) 18
        ^
main.cpp:10:9: note: previous definition is here
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
        ^
1 warning generated.
0.006 s 1 KBi
#2
Correcto 
                      main.cpp:56:9: warning: 'dbg' macro redefined [-Wmacro-redefined]
#define dbg(...) 18
        ^
main.cpp:10:9: note: previous definition is here
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
        ^
1 warning generated.
0.006 s 1 KBi
#3
Correcto 
                      main.cpp:56:9: warning: 'dbg' macro redefined [-Wmacro-redefined]
#define dbg(...) 18
        ^
main.cpp:10:9: note: previous definition is here
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
        ^
1 warning generated.
0.007 s 1 KBi
#4
Correcto 
                      main.cpp:56:9: warning: 'dbg' macro redefined [-Wmacro-redefined]
#define dbg(...) 18
        ^
main.cpp:10:9: note: previous definition is here
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
        ^
1 warning generated.
0.006 s 1 KBi
#5
Correcto 
                      main.cpp:56:9: warning: 'dbg' macro redefined [-Wmacro-redefined]
#define dbg(...) 18
        ^
main.cpp:10:9: note: previous definition is here
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
        ^
1 warning generated.
0.006 s 1 KBi
#6
Correcto 
                      main.cpp:56:9: warning: 'dbg' macro redefined [-Wmacro-redefined]
#define dbg(...) 18
        ^
main.cpp:10:9: note: previous definition is here
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
        ^
1 warning generated.
0.006 s 1 KBi
#7
Correcto 
                      main.cpp:56:9: warning: 'dbg' macro redefined [-Wmacro-redefined]
#define dbg(...) 18
        ^
main.cpp:10:9: note: previous definition is here
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
        ^
1 warning generated.
0.006 s 1 KBi
#8
Correcto 
                      main.cpp:56:9: warning: 'dbg' macro redefined [-Wmacro-redefined]
#define dbg(...) 18
        ^
main.cpp:10:9: note: previous definition is here
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
        ^
1 warning generated.
0.02 s 1 KBi
#9
Correcto 
                      main.cpp:56:9: warning: 'dbg' macro redefined [-Wmacro-redefined]
#define dbg(...) 18
        ^
main.cpp:10:9: note: previous definition is here
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
        ^
1 warning generated.
0.022 s 1 KBi
#10
Correcto 
                      main.cpp:56:9: warning: 'dbg' macro redefined [-Wmacro-redefined]
#define dbg(...) 18
        ^
main.cpp:10:9: note: previous definition is here
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
        ^
1 warning generated.
0.022 s 1 KBi
#11
Correcto 
                      main.cpp:56:9: warning: 'dbg' macro redefined [-Wmacro-redefined]
#define dbg(...) 18
        ^
main.cpp:10:9: note: previous definition is here
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
        ^
1 warning generated.
0.029 s 1 KBi
#12
Correcto 
                      main.cpp:56:9: warning: 'dbg' macro redefined [-Wmacro-redefined]
#define dbg(...) 18
        ^
main.cpp:10:9: note: previous definition is here
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
        ^
1 warning generated.
0.026 s 1 KBi
#13
Correcto 
                      main.cpp:56:9: warning: 'dbg' macro redefined [-Wmacro-redefined]
#define dbg(...) 18
        ^
main.cpp:10:9: note: previous definition is here
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
        ^
1 warning generated.
0.029 s 1 KBi
#14
Correcto 
                      main.cpp:56:9: warning: 'dbg' macro redefined [-Wmacro-redefined]
#define dbg(...) 18
        ^
main.cpp:10:9: note: previous definition is here
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
        ^
1 warning generated.
0.02 s 1 KBi
#15
Correcto 
                      main.cpp:56:9: warning: 'dbg' macro redefined [-Wmacro-redefined]
#define dbg(...) 18
        ^
main.cpp:10:9: note: previous definition is here
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
        ^
1 warning generated.
0.025 s 1 KBi
#16
Correcto 
                      main.cpp:56:9: warning: 'dbg' macro redefined [-Wmacro-redefined]
#define dbg(...) 18
        ^
main.cpp:10:9: note: previous definition is here
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
        ^
1 warning generated.
0.021 s 1 KBi
#17
Correcto 
                      main.cpp:56:9: warning: 'dbg' macro redefined [-Wmacro-redefined]
#define dbg(...) 18
        ^
main.cpp:10:9: note: previous definition is here
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
        ^
1 warning generated.
0.023 s 1 KBi
#18
Correcto 
                      main.cpp:56:9: warning: 'dbg' macro redefined [-Wmacro-redefined]
#define dbg(...) 18
        ^
main.cpp:10:9: note: previous definition is here
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
        ^
1 warning generated.
0.019 s 1 KBi
Puntos totales: 100 / 100

Código

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define forn(i, a, b) for (int i = a; i < b; ++i)
#define SZ(x) int(x.size())
#define pb push_back
#define F first
#define S second
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
void dbg_out() { cerr << endl; }
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
  cerr << ' ' << H;
  dbg_out(T...);
}

ll INF = -1e18;
int n, m;
const int MAX_N = 100, MAX_M = 100;
ll values[MAX_N][MAX_M];

ll max_range_sum2D() {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (i > 0) values[i][j] += values[i - 1][j];
      if (j > 0) values[i][j] += values[i][j - 1];
      if (i > 0 && j > 0) values[i][j] -= values[i - 1][j - 1];
    }
  }
  ll max_mat = INF;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      for (int h = i; h < n; h++) {
        for (int k = j; k < m; k++) {
          ll sub_mat = values[h][k];
          if (i > 0) sub_mat -= values[i - 1][k];
          if (j > 0) sub_mat -= values[h][j - 1];
          if (i > 0 && j > 0) sub_mat += values[i - 1][j - 1];
          max_mat = max(sub_mat, max_mat);
        }
      }
    }
  }
  return max_mat;
}

int main() {
#ifdef LOCAL
  freopen("a.txt", "r", stdin);
// freopen("main.txt", "w", stdout);
#else
  ios::sync_with_stdio(0);
  cin.tie(0);
#define endl '\n'
#define dbg(...) 18
#endif
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) cin >> values[i][j];
  }
  cout << max_range_sum2D() << endl;
  return 0;
}