1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
def minimalna_liczba_obrazow(h, w, rozmiary_obrazow):
    rozmiary_obrazow.sort(reverse=True)
    memo = {}  # Słownik do przechowywania wyników podproblemów

    def oblicz(h, w, index=0):
        # Klucz memoizacji oparty o aktualne parametry
        klucz_memo = (h, w, index)
        if klucz_memo in memo:
            return memo[klucz_memo]

        if h == 0 or w == 0:
            return 0
        if index == len(rozmiary_obrazow):
            memo[klucz_memo] = float('inf')
            return memo[klucz_memo]
        
        rozmiar = rozmiary_obrazow[index]
        min_obrazy = float('inf')
        if h // rozmiar > 0 and w // rozmiar > 0: 
            liczba_obrazow = (h // rozmiar) * (w // rozmiar)
            pozostala_h = h % rozmiar
            pozostala_w = w % rozmiar
            
            # Pokrycie pozostałej przestrzeni pionowej, potem pozostałej poziomej, ale bez części wspólnej.
            pionowo_poziomo = liczba_obrazow + oblicz(pozostala_h, w, index + 1) + oblicz(h - pozostala_h, pozostala_w, index + 1)
            
            # Pokrycie pozostałej przestrzeni poziomej, potem pozostałej pionowej, ale bez części wspólnej.
            poziomo_pionowo = liczba_obrazow + oblicz(h, pozostala_w, index + 1) + oblicz(pozostala_h, w - pozostala_w, index + 1)
            
            min_obrazy = min(pionowo_poziomo, poziomo_pionowo)
        else:
            min_obrazy = oblicz(h, w, index + 1)
        
        memo[klucz_memo] = min_obrazy
        return min_obrazy
    
    wynik = oblicz(h, w)
    return wynik if wynik != float('inf') else -1

if __name__ == "__main__":
    h, w = map(int, input().split())
    n = int(input())
    arr = list(map(int, input().split()))
    print(minimalna_liczba_obrazow(h, w, arr))