colheita-de-milho

OPEI 2019 - Colheita de Milho

Michilinho é um garoto que mora na roça e sempre ajuda o seu pai a colher os milhos de sua plantação. Entretanto, a plantação possui ruas onde nem todas as espigas de milho estão maduras o suficiente para serem colhidas. A fim de otimizar seu tempo, Michilinho quer entrar nas ruas de tal forma que, ao chegar no final do terreno, ele vai ter colhido o máximo de milhos possíveis, para em seguida poder jogar bola com seus amigos.

Ele tem uma dificuldade a mais que é: ele só pode ir para as ruas à direita ou abaixo dele.

O terreno da plantação é representado por uma matriz N x M, onde cada célula possui o valor de quantos milhos prontos para serem colhidos se encontram naquela rua. O seu papel é ajudar Michilinho a chegar ao final do terreno, célula N-1 x M-1, com o máximo de milhos possíveis. Considere que ele começa sempre da posição inicial da matriz (linha 0, coluna 0).

Entrada ⬅️

Dois números N e M que representam as dimensões do terreno N x M. Em seguida, serão lidas N linhas com M números cada, contendo o número K de milhos prontos a serem colhidos naquela rua.

Saída ➡️

O maior número possível de milhos a serem colhidos.

Restrições:

• 0 ≤ N, M ≤ 10
• 0 ≤ K ≤ 10⁶

---

Exemplos:

• Primeiro Exemplo

  Entrada:

  3 2
  5 10
  1 2
  20 3
  

  Saída:

  29
  

• Segundo Exemplo

  Entrada:

  3 3
  2 5 96
  72 0 5
  14 26 1
  

  Saída:

  115
  

Soluções adicionadas:

Ícone	Linguagem	Tag	Nome
	Python	@fabiopapais	Fábio Papais