Fişierul intrare/ieşire:balans.in, balans.outSursăpreONI 2006 Runda 1
AutorMircea Bogdan PasoiAdăugată de
Timp execuţie pe test1.75 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Balans

Bronzarel a iesit din spital si este sanatos acum. Imediat dupa ce a iesit s-a intalnit din nou cu bunul sau prieten Zaharel si acestia s-au pus pe rezolvat probleme! Una din problemele pe care au incercat s-o rezolve s-a dovedit prea dificila pentru ei, de aceea vor avea nevoie de ajutorul tau.

Fie A o matrice de numere naturale cu N linii si M coloane. Vom defini o matrice B de marime P*Q ca fiind o submatrice a matricii A daca exista numerele (x,y) astfel incat Bi,j = Ai+x,j+y pentru 1≤i≤P si 1≤j≤Q. De asemenea, vom defini balansul unei matrici ca fiind raportul dintre suma tuturor elementelor din matrice si numarul acestora.

Problema la care s-au chinuit Zaharel si Bronzarel cere sa se determine o submatrice de balans maxim a matrici A, care are cel putin R randuri si C coloane. Fiindca lucrurile nu sunt niciodata asa de "simple", matricea A nu este o matrice oarecare, ci una chiar foarte speciala, si anume randurile si coloanele matricii pot fi permutate circular.

Cerinta

Determinati submatricea de balans maxim dintr-o matrice data, tinand cont ca randurile si coloanele pot fi permutate circular inainte pentru a obtine un rezultat cat mai favorabil.

Date de Intrare

Prima linie din fisierul balans.in va contine numerele N,M,R,C reprezetand dimensiunea matricii A si limitele inferioare ale dimensiunilor submatricii cerute. Urmatoarele N linii vor contine cate M numere naturale.

Date de Iesire

Fiserul balans.out va contine pe o singura linie o valoare reprezentand balansul maxim posibil al unei submatrici. Rezultatul va fi afisat cu 3 zecimale exacte.

Restrictii si observatii

  • 1 ≤ N, M ≤ 150
  • 0 ≤ R ≤ N
  • 0 ≤ C ≤ M
  • 0 ≤ Ai,j ≤ 100.000

Exemplu

balans.inbalans.out
3 4 2 1
15 5 15 8
1 2 1 3
4 8 8 4
11.500

Explicatie

Se permuta circular odata randurile si se obtine matricea:
1  2 1  3
4  8 8  4
15 5 15 8
Submatricea de balans maxim este ingrosata.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content