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
45
46
47
48
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int findMinPaintings(long long h, long long w, const vector<int>& sizes, int index) {
    if (h == 0 || w == 0) return 0; // Brak przestrzeni do pokrycia.
    if (index == sizes.size()) return 1e9; // Nie można pokryć przestrzeni dostępnymi obrazami.

    int size = sizes[index];
    int minPaintings = 1e9;

    // Sprawdzanie, ile maksymalnie obrazów aktualnego rozmiaru można użyć
    for (int i = 0; i * size <= h; ++i) {
        for (int j = 0; j * size <= w; ++j) {
            // Liczba obrazów potrzebna do pokrycia pozostałej części ściany
            int requiredPaintings = findMinPaintings(h - i * size, w, sizes, index + 1) +
                findMinPaintings(i * size, w - j * size, sizes, index + 1);

            if (i * j > 0) requiredPaintings += i * j; // Dodanie obrazów, jeśli są używane

            minPaintings = min(minPaintings, requiredPaintings);
        }
    }

    return minPaintings;
}

int main() {
    long long h, w;
    int n;
    cin >> h >> w >> n;

    vector<int> d(n);
    for (int i = 0; i < n; ++i) {
        cin >> d[i];
    }

    sort(d.rbegin(), d.rend()); // Sortowanie rozmiarów obrazów od największego do najmniejszego

    int result = findMinPaintings(h, w, d, 0);

    if (result >= 1e9) cout << "-1\n";
    else cout << result << endl;

    return 0;
}