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

Envío 1292

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

  • Autor: judavid.arias
  • Fecha: 2020-10-19 00:12:48 UTC (Hace alrededor de 2 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 1 KBi
#4
Correcto
0.005 s 7 KBi
#5
Correcto
0.004 s 1 KBi
#6
Correcto
0.005 s 1 KBi
#7
Incorrecto
0.005 s 1 KBi
#8
Correcto
0.006 s 1 KBi
#9
Correcto
0.005 s 1 KBi
#10
Correcto
0.006 s 1 KBi
#11
Correcto
0.004 s 1 KBi
#12
Incorrecto
0.006 s 1 KBi
#13
Incorrecto
0.005 s 1 KBi
#14
Incorrecto
0.006 s 1 KBi
#15
Correcto
0.006 s 3 KBi
#16
Correcto
0.003 s 1 KBi
#17
Incorrecto
0.005 s 1 KBi
#18
Correcto
0.005 s 1 KBi
Puntos totales: 73 / 100

Código

#include <iostream>
#include <algorithm>    // std::max
#include <bits/stdc++.h>
using namespace std;

int main()
{
	int R, C;
	cin >> R;
	cin >> C;
	int matrix[R][C];
	int sums[R][C];
	for(int i = 0;i<R;i++)
	{
		for(int j = 0;j<C;j++)
		{
			cin >> matrix[i][j];
		}
	}
	
	int sumRow = 0;
	for(int i = 0;i<R;i++)
	{
		sumRow = 0;
		for(int j = 0;j<C;j++)
		{
			sumRow += matrix[i][j];
			if(i-1 >= 0)
				sums[i][j] = sumRow + sums[i-1][j];
			else
				sums[i][j] = sumRow;
		}
	}
	
	int max1 = INT_MIN;
	for(int i = 0;i<R;i++)
	{
		sumRow = 0;
		for(int j = 0;j<C;j++)
		{
			int sideLeftUp = sums[i][j];
			int sideRightUp;
			if(j+1 < C)
				sideRightUp = sums[i][C-1] - sideLeftUp;
			else
				sideRightUp = sums[i][C-1];
			int sideLeftDown;
			if(i+1 < R)
				sideLeftDown = sums[R-1][j] - sideLeftUp;
			else
				sideLeftDown = sums[R-1][j];
			
			int sideRightDown = sums[R-1][C-1];
			if(j+1 < C)
				sideRightDown += - sideLeftUp;
			if(i+1 < R)
				sideRightDown += -sideLeftDown;
			max1 = max(max1, sideLeftUp);
			max1 = max(max1, sideRightUp);
			max1 = max(max1, sideLeftDown);
			max1 = max(max1, sideRightDown);
		}
	}
	
	max1 = max(max1, sums[R-1][C-1]);
	cout <<  max1 << endl;

	return 0;
	
	
}