Solução Informática Intermediário - Semana 45

Solução de Frederico Bulhões

Para resolver esse problema devemos usar soma de colunas e linhas para encontrar a melhor posição rapidamente. Primeiramente vamos ler a matriz $m[i][j]$ , onde a posição $(i,j)$ , indica o $X_{i,j}$ . Além disso vamos cirar dois vetors, $linha[i]$ e $coluna[j]$ , onde $linha[i]$ , indica a soma de todos os $X_{ij}$ na linha $i$ , e $coluna[j]$ , indica a soma das $X_{ij}$ na coluna $j$ . Agora podemos passar por todas as posições $(i,j)$ , e ver o máximo de $coluna[i]+linha[j]-2\cdot m[i][j]$ , subtraindo $m[i][j]$ duas vezes pois está sendo contado duas vezes a mais.

Assim achando o máximo dessa expressão para todo $(i,j)$ , temos a resposta da questão.

Código para melhor entendimento:

	//solucao de Carolina Cmvc

	#include <bits/stdc++.h>

	using namespace std;

	#define MAXN 1005

	int main()
	{
	ios_base::sync_with_stdio(false);
	int n, m[MAXN][MAXN], l[MAXN], c[MAXN];
	cin>>n;
	for (int i=0;i<n;i++)
	{
	int sum=0;
	for (int j=0;j<n;j++){
	cin>>m[i][j];
	sum+=m[i][j];
	}
	l[i] = sum;
	}
	for (int j=0;j<n;j++)
	{
	int sum = 0;
	for (int i=0;i<n;i++) sum+=m[i][j];
	c[j] = sum;
	}
	int maior_peso=0;
	for (int i=0;i<n;i++)
	{
	for (int j=0;j<n;j++){
	m[i][j]=c[j]+l[i]-2*m[i][j];
	maior_peso = max(maior_peso, m[i][j]);
	}
	}
	cout<<maior_peso<<endl;
	}

view raw

torre.cpp

hosted with ❤ by GitHub