Misolovke
vreme | memorija | ulaz | izlaz |
---|---|---|---|
1 s | 1000 Mb | standardni izlaz | standardni ulaz |
Mirko ima problem sa miševima, i otišao je kod Slavka da pozajmi mišolovke. Nažalost, i Slavko ima problem sa miševima, i postavio je mišolovke po svom podrumu (koji je popločan i kvadratnog oblika), tako da na svakoj pločici stoji barem jedna mišolovka. Pao je dogovor da sa svakog reda pločica Mirko uzme sve mišolove sa K uzastopnih pločica u tom redu, ali tako da nakon uzimanja mišolovka ne postoji putanja za miševe sa sa prednjeg zida gde je ulaz do zadnjeg zida gde Slavko čuva zimnicu (smatra se da postoji put ako postoji niz pločica bez mišolovki gde svake 2 uzastopne pločice dele 1 stranu). Pomozite Mirku da izabere pločice sa kojih uzima mišolovke tako da uzme najveći mogući broj mišolovki.
Prvi red ulaza sadrži broj N koji predstavlja dimenzije podruma i K koji predstavlja sa koliko pločica može mirko da uzme mišolovka u svakom redu.
U sledećih N redova se nalai N celih brojeva m[i,j] koji predstavljaju broj mišolovki na datoj pločici u datom redu.
Jedan ceo broj koji predstavlja najveći broj mišolovki koje Mirko može da uzme.
1 < N <= 250
0 < K < N / 2
0 <= m[i,j] <= 1000
4 2
5 5 1 1
1 5 5 1
1 5 5 1
5 5 1 1
36
Jedan od mogućih načina je da Mirko uzme iz prvog reda 5 mišolovki sa prve pločice i 5 sa druge (1,1) i (1, 2), iz drugog reda 5 sa treće pločice i 1 sa četvrte pločice (2,3) i (2,4), iz trećeg reda 5 sa druge i 5 sa treće (3,2) I (3,3), iz četvrtok reda 5 sa prve i 5 sa druge (4,1), (4,2)
5 5 1 1
1 5 5 1
1 5 5 1
5 5 1 1
5 5 1 1
1 5 5 1
1 5 5 1
5 5 1 1
Morate biti ulogovani kako biste poslali zadatak na evaluaciju.