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

Envío 2349

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

  • Autor: andreslel
  • Fecha: 2020-12-14 16:44:16 UTC (Hace más de 3 años)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.004 s 1 KBi
#2
Correcto
0.005 s 1 KBi
#3
Correcto
0.006 s 1 KBi
#4
Correcto
0.004 s 1 KBi
#5
Correcto
0.003 s 1 KBi
#6
Correcto
0.005 s 1 KBi
#7
Correcto
0.004 s 1 KBi
#8
Correcto
0.026 s 1 KBi
#9
Correcto
0.027 s 2 KBi
#10
Correcto
0.026 s 1 KBi
#11
Correcto
0.03 s 1 KBi
#12
Correcto
0.022 s 1 KBi
#13
Correcto
0.026 s 1 KBi
#14
Correcto
0.02 s 1 KBi
#15
Correcto
0.022 s 1 KBi
#16
Correcto
0.02 s 1 KBi
#17
Correcto
0.02 s 1 KBi
#18
Correcto
0.017 s 1 KBi
Puntos totales: 100 / 100

Código

#include<stdio.h>
#define max(x,y)(x > y? x:y)
#define ll long long

int main(){
    int n,m;
    scanf(" %d %d",&n,&m);
    ll matrix[n][m];
    for(int i = 0; i < n;++i)
        for(int j = 0; j < m; ++j)
            scanf(" %lld",&matrix[i][j]);
    for(int i = 0; i < n;++i){
        for(int j = 0; j < m;++j){
            if(j)
                matrix[i][j] += matrix[i][j-1];
            if(i)
                matrix[i][j] += matrix[i-1][j];
            if(i && j)
                matrix[i][j] -= matrix[i-1][j-1];
        }
    }
    ll ans = -100000000000LL;
    for(int i = 0; i < n;++i){
        for(int j = 0; j < m;++j){
            for(int q = i; q < n;++q){
                for(int k = j; k < m; ++k){
                    ll check = matrix[q][k];
                    if(j)
                        check -= matrix[q][j-1];
                    if(i)
                        check -= matrix[i-1][k];
                    if(i && j)
                        check += matrix[i-1][j-1];
                    ans = max(check,ans);
                }
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}