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
//Jakub Trela
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

LL n;
vector<LL> tab;

map<pair<LL,LL>,LL> m;

LL rek(LL h,LL w){
    if(h>w)swap(h,w);
    if(h==0)return 0;
    if(m.find({h,w})!=m.end())return m[{h,w}];
    for(LL i=n-1;i>=0;i--){
        if(tab[i]<=h){
            LL w1=rek(h%tab[i],w-w%tab[i]);
            LL w2=rek(h-h%tab[i],w%tab[i]);
            LL w3=rek(h%tab[i],w%tab[i]);
            if(w1==-1 || w2==-1 || w3==-1){m[{h,w}]=-1;return -1;}
            m[{h,w}]=w1+w2+w3+((h/tab[i]))*((w/tab[i]));
            return w1+w2+w3+((h/tab[i]))*((w/tab[i]));
        }
    }
    m[{h,w}]=-1;
    return -1;
}

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

    LL h,w;
    cin>>h>>w;

    cin>>n;

    tab.resize(n);

    for(LL i=0;i<n;i++)cin>>tab[i];

    cout<<rek(h,w)<<endl;

    return 0;
}