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
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <iostream>
#include <map>
#include <utility>

using namespace std;

map<pair<int, int>, long long> cache {};

long long cover(int h, int w, int *pic, int li) {
    int ch {}, cw {};
    if (h < w) {
        ch = h;
        cw = w;
    } else {
        ch = w;
        cw = h;
    }
    pair<int, int> p {make_pair(ch, cw)};
    map<pair<int, int>, long long>::iterator it {};
    it = cache.find(p);
    if (it != cache.end()) {
        return it->second;
    }

    //cout << "cover: h=" << h << " w=" << w << '\n';
    if (h % pic[0] != 0 || w % pic[0] != 0) {
        //cout << "resultA: " << -1 << '\n';
        cache[p] = -1;
        return -1;
    }

    if (h == pic[0]) {
        //cout << "resultB: " << w / pic[0] << '\n';
        cache[p] = w / pic[0];
        return w / pic[0];
    }

    if (w == pic[0]) {
        //cout << "resultC: " << h / pic[0] << '\n';
        cache[p] = h / pic[0];
        return h / pic[0];
    }

    int i {li};
    long long count1 {};
    long long count2 {};
    long long count3 {};
    long long count4 {};

    while (i >= 0) {
        count1 = 0;
        count2 = 0;
        count3 = 0;
        count4 = 0;
        if (pic[i] > h || pic[i] > w) {
            i--;
            continue;
        }

        if (pic[i] == h && pic[i] == w) {
            //cout << "resultD: " << 1 << '\n';
            cache[p] = 1;
            return 1;
        } else if(pic[i] == h) {
            count1 = cover(h, w - pic[i], pic, i);
        } else if(pic[i] == w) {
            count1 = cover(h - pic[i], w, pic, i);
        }

        if (count1 > 0) {
            //cout << "resultE: " << 1 + count1 << '\n';
            cache[p] = 1 + count1;
            return 1 + count1;
        }

        if (pic[i] < h && pic[i] < w) {
            count1 = cover(h - pic[i], w, pic, i);
            if (count1 > 0) {
                count2 = cover(pic[i], w - pic[i], pic, i);
            }

            count3 = cover(h - pic[i], pic[i], pic, i);
            if (count3 > 0) {
                count4 = cover(h, w - pic[i], pic, i);
            }

            if (count1 > 0 && count2 > 0 && count3 > 0 && count4 > 0) {
                if (count1 + count2 < count3 + count4) {
                    //cout << "resultF: " << 1 + count1 + count2 << '\n';
                    cache[p] = 1 + count1 + count2;
                    return 1 + count1 + count2;
                } else {
                    //cout << "resultG: " << 1 + count3 + count4 << '\n';
                    cache[p] = 1 + count3 + count4;
                    return 1 + count3 + count4;
                }
            }

            if (count1 < 0 || count2 < 0) {
                if (count3 > 0 && count4 > 0) {
                    //cout << "resultH: " << 1 + count3 + count4 << '\n';
                    cache[p] = 1 + count3 + count4;
                    return 1 + count3 + count4;
                }
            }

            if (count3 < 0 || count4 < 0) {
                if (count1 > 0 && count2 > 0) {
                    //cout << "resultI: " << 1 + count1 + count2 << '\n';
                    cache[p] = 1 + count1 + count2;
                    return 1 + count1 + count2;
                }
            }

        }
        i--;
    }

    cache[p] = -1;
    return -1;

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int h {}, w {}, n {};
    cin >> h;
    cin >> w;
    cin >> n;

    int *pic {new int[n]};

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

    cout << cover(h, w, pic, n - 1);

    return 0;
}