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
#include<cstdio>
#include<vector>
#include<utility>

using namespace std;

int main() {
    long height;
    long width;
    scanf("%ld %ld\n", &height, &width);

    int pictureTypesCount;
    scanf("%d\n", &pictureTypesCount);

    vector<long> pictures;
    for (int i = 0; i < pictureTypesCount; i++) {
        long picture;
        scanf("%ld", &picture);

        pictures.push_back(picture);
    }

    if (height % pictures[0] != 0 || width % pictures[0] != 0) {
        printf("-1\n");
        return 0;
    }

    int largestIx = pictures.size() - 1;
    long sum = 0;
    
    vector<pair<long, long> > segments;
    vector<pair<long, long> > nextSegments;

    pair<long, long> wholeWall(height, width);
    segments.push_back(wholeWall);

    while (!segments.empty()) {
        for (int i = 0; i < segments.size(); i++) {
            long sHeight = segments[i].first;
            long sWidth = segments[i].second;

            long fittedInH = sHeight / pictures[largestIx];
            long fittedInW = sWidth / pictures[largestIx];

            long fitted = fittedInH * fittedInW;
           
            sum += fitted;

            if (fitted == 0) {
                nextSegments.push_back(segments[i]);
            } else {
                long hRemainder = sHeight % pictures[largestIx];
                if (hRemainder > 0) {
                    pair<long, long> lowSegment(hRemainder, fittedInW * pictures[largestIx]);
                    nextSegments.push_back(lowSegment);
                }

                long wRemainder = sWidth % pictures[largestIx];
                if (wRemainder > 0) {
                    pair<long, long> rightSegment(sHeight, wRemainder);
                    nextSegments.push_back(rightSegment);
                }
            }
            
        }

        largestIx--;

        segments = nextSegments;

        vector<pair<long, long> > next;
        nextSegments = next;
    }

    printf("%ld\n", sum);

    return 0;
}