Dònuts P98480
Sigui m un natural estrictament positiu. Direm que un dònut de mida m és un quadrat de 3m × 3m caselles aliniat amb els eixos horitzontal i vertical al qual se li ha esborrat el quadrat central de mida m × m. Per exemple, això són dònuts per a m=1, m=2 i m=3:
XXX XXXXXX XXXXXXXXX
X X XXXXXX XXXXXXXXX
XXX XX XX XXXXXXXXX
XX XX XXX XXX
XXXXXX XXX XXX
XXXXXX XXX XXX
XXXXXXXXX
XXXXXXXXX
XXXXXXXXX
Donada una matriu n × n de naturals, i una m entre 1 i n/3, heu de situar un dònut de mida m sobre la matriu, de manera que totes les 8m2 caselles del dònut estiguin dins de la matriu, i que els naturals coberts pel dònut tinguin la màxima suma possible.
Entrada
L’entrada consisteix en diversos casos, cadascun amb n i m, seguides d’n files, cadascuna amb n enters entre 0 i 109. Podeu suposar 3 ≤ n ≤ 1000 i 1 ≤ m ≤ n/3.
Sortida
Per a cada cas, escriviu la màxima suma possible dels nombres de la matriu coberts per un dònut de mida m.
Pista
La solució esperada té cost Θ(n2).
Input
3 1 500000000 500000000 500000000 500000000 999999999 500000000 500000000 500000000 500000000 8 2 2 3 4 5 5 4 3 2 1 1 1 1 1 1 1 1 1 9 9 9 9 9 9 1 1 9 5 5 5 5 9 1 1 9 5 7 7 5 9 1 1 9 5 7 7 5 9 1 1 9 5 5 5 5 9 1 1 9 9 9 9 9 9 1 10 1 0 1 2 3 4 5 6 7 8 9 35 36 37 38 39 40 41 42 43 10 34 63 64 65 66 67 68 69 44 11 33 62 83 84 85 86 87 70 45 12 32 61 82 95 96 97 88 71 46 13 31 60 81 94 99 98 89 72 47 14 30 59 80 93 92 91 90 73 48 15 29 58 79 78 77 76 75 74 49 16 28 57 56 55 54 53 52 51 50 17 27 26 25 24 23 22 21 20 19 18 10 3 0 1 2 3 4 5 6 7 8 9 35 36 37 38 39 40 41 42 43 10 34 63 64 65 66 67 68 69 44 11 33 62 83 84 85 86 87 70 45 12 32 61 82 95 96 97 88 71 46 13 31 60 81 94 99 98 89 72 47 14 30 59 80 93 92 91 90 73 48 15 29 58 79 78 77 76 75 74 49 16 28 57 56 55 54 53 52 51 50 17 27 26 25 24 23 22 21 20 19 18
Output
4000000000 240 756 3924
- Author
- Salvador Roura
- Language
- Catalan
- Official solutions
- C++
- User solutions
- C++