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
#include <bits/stdc++.h>

using namespace std;

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


    // first in pair is width of the rectangle second is height
    queue<pair<int, int>> proccessQue;


    int originalHeight, originalWidth;
    cin >> originalWidth >> originalHeight;

    long long int pole = static_cast<long long int>(originalHeight) * originalWidth;

    int n;
    cin >> n;
    
    vector<int> paintings(n);
    for(int i {}; i < n; ++i) cin >> paintings[i];
    sort(paintings.begin(), paintings.end());

    proccessQue.push(pair<int, int>(originalWidth, originalHeight));



    int height, width;
    
    int newRectangleH, newRectangleW;
    bool found;
    
    long long int resultCt{}, second{};

    int th, tw;
    while(proccessQue.empty() == false)
    {

        found = false;
        height = proccessQue.front().second;
        width = proccessQue.front().first;
        proccessQue.pop();




        // search for the biggest rectangle that we can put on the original rectangle

        for(int i {n-1}; i >= 0; --i)
        {
            
            newRectangleH = (static_cast<long long int>(height/paintings[i])) * paintings[i];
            newRectangleW = (static_cast<long long int>(width/paintings[i]))  * paintings[i];
            if(newRectangleH != 0 && newRectangleW!= 0)
            {

                resultCt += (static_cast<long long int>(height/paintings[i])) * (width/paintings[i]);
                found = true;

                break;
            }
        }
        
        if(!found)
            continue;

        pole -= static_cast<long long int>(newRectangleH) * newRectangleW;

        // oblicz dwa pozosotale prostokaty i dodaj do que

        tw = width - newRectangleW;
        if(tw > 0)
            proccessQue.push(pair<int, int>(tw, height));

        th = height-newRectangleH;
        if(th > 0)
            proccessQue.push(pair<int, int>(newRectangleW, th));
    }


    if(!pole)
        cout << resultCt << '\n';
    else cout << "-1" << '\n';
}