Fişierul intrare/ieşire:livada2.in, livada2.outSursăONIS 2015, Runda 1
AutorMihai NituAdăugată deThe_Viper_The_Mountain_And_The_ImpUNIBUC Impaler-009 Challenge costyv87 The_Viper_The_Mountain_And_The_Imp
Timp execuţie pe test2.4 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Por Costel si Livada

Por Costel a descoperit o scriere din mitologia porceasca: “Balada Porcului”. Balada descrie o poveste de dragoste dintre un porc si o purcica. Intr-unul din capitole, porcul vrea sa-si impresioneze aleasa prin ridicarea unui cotet. Nu reuseste, insa, limitat fiind de eterna sa conditie de porc. Dar acesta spune apoi ca:

  Am gasit, insa, la urma,
  O livada cat o ferma,
  Ascunsa-n inima padurii,
  Strapunsa de lumina lunii,
  Si o tufa drept cotet
  Pentru porcul iubaret.

Por Costel nu este impresionat, insa, nici de rimele fortate, nici de figurile de stil exagerate. “O padure e plina de livezi” zice el, “se pune problema doar cum o alegi”.

Se da o matrice de N linii si M coloane ce descrie o “padure”. Fiecare celula are o valoare intreaga (pozitiva sau negativa) - gradul de frumusete al acelei celule. Se cere alegerea unei “livezi” adica o submultime de celule care satisface criteriile:

  • Este nevida
  • Este “conexa” (adica se poate ajunge dintr-o celula in oricare alta trecand numai prin celule care au o latura comuna)
  • Intersectia submultimii cu o linie a matricei este fie multimea vida, fie o secventa “conexa” (aceeasi definitie ca mai sus) de celule. Cu alte cuvinte, pe fiecare linie, submultimea are fie nicio celula, fie un interval continuu de celule.

Dintre toate submultimile de celule cu aceasta proprietate, va cerem sa o alegeti pe cea cu suma gradelor de frumusete maxima.

Date de intrare

Fişierul de intrare livada2.in va contine pe prima linie T, numarul de teste.
Fiecare din cele T teste are formatul urmator: pe prima linie, cor fi doua numere naturale N si M, numarul de linii si numarul de coloane al matricei. Pe urmatoarele N linii vor fi afisate cate M numere separate prin spatii. Al j-lea numar de pe a i-a linie semnifica gradul de frumusete al celulei (i,j).

Date de ieşire

În fişierul de ieşire livada2.out se vor afisa T linii iar fiecare dintre acestea va contine un singur numar intreg, suma maxima a gradelor de frumusete a unei livezi.

Restricţii

  • T5
  • 1M,N300
  • -10^4 ≤ gradul de frumusete al unei celule ≤ 10^4

Exemplu

livada2.inlivada2.out
1
3 4
5 -3 0 0
-2 3 3 4
-7 -6 4 -5
17

Explicaţie

Livada contine celulele (1,1), (2,1), (2,2), (2,3), (2,4), (3,3)

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content