28a Olimpíada Brasileira de Informática
Jogo do Poder
Jonathan está empolgado com a nova sensação do momento: o Jogo do Poder. Este jogo é jogado em uma matriz de N linhas e M colunas, na qual cada célula possui um monstro. O monstro na linha i e coluna j possui poder P_{i,j}. No início do jogo, Jonathan escolhe um dos N × M monstros para jogar. O monstro escolhido por Jonathan se torna o herói do jogo e começa o jogo com o poder indicado em sua célula. Jonathan pode mover o herói ortogonalmente (isto é, para cima, baixo, direita ou esquerda) na matriz enquanto o herói estiver vivo. O herói não pode sair da matriz, mas pode visitar a mesma célula múltiplas vezes. Toda vez que o herói entra em uma célula com um monstro vivo, ocorre uma batalha entre o herói e o monstro da célula. O herói ganha a batalha se, e somente se, o seu poder for maior ou igual ao poder do monstro. Caso contrário, o herói morre e perde o jogo em game over. Toda vez que o herói ganha uma batalha, o monstro derrotado morre (ou seja, a célula não possui mais nenhum monstro) e, como recompensa, o poder do monstro é somado ao poder do herói (ou seja, se o herói matar o monstro da célula (i,j), o poder do herói aumenta em P_{i,j}). Jonathan percebeu que o jogo pode ser injusto: mesmo que ele jogue de maneira ótima, dependendo de sua escolha de herói, pode ser possível matar todos os monstros, apenas alguns ou até mesmo nenhum monstro. Decidido a "platinar" o jogo, Jonathan precisa saber o poder máximo que cada herói consegue alcançar (ou seja, o poder máximo possível de ser atingido ao iniciar o jogo em cada célula da matriz) se o jogo for jogado de forma ótima. Felizmente, ele descobriu que os alunos da OBI (Organização dos Bons Informáticos) recentemente resolveram o Jogo da Vida, seu terceiro jogo favorito (atrás do Jogo do Poder e do Jogo de Corrida, claro), então ele pediu a sua ajuda novamente! Determine, para cada herói, o poder máximo que ele consegue alcançar caso Jonathan jogue de forma ótima.Entrada
A primeira linha de entrada contém dois inteiros N e M, o número de linhas e o número de colunas da matriz, respectivamente. As próximas N linhas contém M inteiros cada. O j-ésimo inteiro da i-ésima linha contém o poder P_{i,j} do monstro na i-ésima linha e j-ésima coluna.Saída
O seu programa deverá imprimir N linhas, cada uma contendo M inteiros. O j-ésimo inteiro da i-ésima linha deve ser o poder máximo que Jonathan consegue alcançar caso ele escolha como herói o monstro da célula (i,j) e jogue de maneira ótima.Restrições
- 1 ≤ N ≤ 100 000
- 1 ≤ M ≤ 100 000
- 1 ≤ N × M ≤ 100 000
- 1 ≤ P_{i,j} ≤ 1 000 000 000 para todo 1 ≤ i ≤ N e 1 ≤ j ≤ M
Informações sobre a pontuação
A tarefa vale 100 pontos. Estes pontos estão distribuídos em subtarefas, cada uma com suas restrições adicionais às definidas acima.- Subtarefa 1 (0 pontos): Esta subtarefa é composta apenas pelos exemplos mostrados abaixo. Ela não vale pontos, serve apenas para que você verifique se o seu programa imprime o resultado correto para os exemplos.
- Subtarefa 2 (11 pontos):
- N=1
- M ≤ 1000
- 1 ≤ P_{1,j} ≤ 2 para todo 1 ≤ j ≤ M
- Subtarefa 3 (13 pontos):
- N=1
- M ≤ 1000
- Subtarefa 4 (29 pontos):
- N=1
- Subtarefa 5 (17 pontos):
- N ≤ 30
- M ≤ 30
- Subtarefa 6 (30 pontos): Sem restrições adicionais.
Exemplos
Entrada
2 3 2 3 9 1 7 200 |
Saída
6 6 22 1 22 222 |
Entrada
1 7 6 3 10 1 20 7 7 |
Saída
9 3 54 1 54 14 14 |
Entrada
5 6 10 10 10 10 10 10 10 10 1 1 1 10 10 10 10 1 10 10 10 10 10 4 10 10 10 10 10 10 10 2 |
Saída
250 250 250 250 250 250 250 250 8 8 8 250 250 250 250 8 250 250 250 250 250 8 250 250 250 250 250 250 250 2 |