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
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(0);
    long long h, w;
    cin >> h >> w;
    int n;
    cin >> n;
    vector <long long> squares;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        squares.push_back(x);
    }
    sort(squares.begin(), squares.end());
    stack <pair <long long, long long> > s;
    s.push({h, w});
    long long result = 0;
    while (!s.empty()) {
        auto p = s.top();
        s.pop();
        
        long long m = min(p.first, p.second);
        if (m < squares[0] || p.second < squares[0]) {
            cout << "-1";
            return 0;
        }
        
        int poc = 0, kon = n - 1, x = 0;
        while (poc <= kon) {
            int sr = (poc+kon)/2;
            if (squares[sr] <= m) {
                x = squares[sr];
                poc = sr + 1;
            }
            else {
                kon = sr - 1;
            }
        }
        
        result += (p.first / x) * (p.second / x) ; 

        if (p.first % x != 0 && p.second % x != 0) {
            s.push({p.first % x, p.second % x});
            s.push({p.first % x, p.second - (p.second % x)});
            s.push({p.first - (p.first%x), p.second % x});
        }
        else if (p.first % x != 0) {
            s.push({p.first % x, p.second});
        }
        else if (p.second % x != 0) {
            s.push({p.first, p.second % x});
        }
    }
    cout << result;
    return 0;
}