Reconnaissance d'ovnis – Épreuve régionale 2012

Niveau 6

Énoncé

Lorsqu'on regarde le ciel, on peut parfois apercevoir un amas de disparités négatives et positives. Le potentiel d'une zone est égal à la somme des énergies s'y trouvant. C'est dans des zones de fort potentiel que l'on décèle parfois des ovnis.

La « zone de ciel » dans laquelle nous cherchons les ovnis est toujours rectangulaire.

On vous demande de déceler le plus fort potentiel présent dans une zone du ciel. Cette zone peut être vide.

Entrée

  • Sur la première ligne, la hauteur N de la carte.
  • Sur la deuxième ligne, la longueur M de la carte.
  • Sur les N lignes suivantes, M nombres représentant les énergies.

Sortie

Le plus fort potentiel que l'on puisse trouver dans une zone de la carte.

Contraintes

  • 1 <= N <= 100
  • 1 <= M <= 1 000

Contraintes d'exécution

Utilisation mémoire maximum
500 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
3
4
-2 1 -1 4
2 -3 5 -7
-3 8 -1 1
Exemple de sortie
9