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:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //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; | |
| } |
Comente