Dònuts P98480


Statement
 

pdf   zip

html

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 ≤ mn/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).

Public test cases
  • 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
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++