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
#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")

#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
#define int ll
using ll = long long;
using ld = long double;  // or double, if TL is tight
using str = string; 
using ii = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;


signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n, w, h;
    cin >> w >> h >> n;
    const int MV = 500;
    vi d(n);
    for(int i = 0; i < n; ++i) cin >> d[i];
    vector<vi> DP(MV, vi(MV, -1));
    DP[0][0] = 0;/// cost 0
    for(auto it : d) DP[it][it] = 1;
    auto improve = [&](int l, int c, int v) {
        if(DP[l][c] == -1) {
            DP[l][c] = v;
            return;
        }
        DP[l][c] = min(DP[l][c], v);
    };

    function<int(int, int)> cost_greedy = [&](int l, int c) {
        if(!l || !c) return 0ll;
        ///reducem greedy din l cu dma
        int pma = -1;
        for(int i = 0; i < d.size(); ++i) {
            if(d[i] <= l) pma = i;
        }
        if(pma == -1) return -1ll;

        int dma = d[pma], cramas = c, cre = 0; 
        for(int i = pma; i >= 0; --i) {
            cre += cramas / d[i] * (dma / d[i]);
            cramas -= cramas / d[i] * d[i];
        }
        int rec = cost_greedy(l - dma, c);
        if(rec == -1) return -1ll;
        return cost_greedy(l - dma, c) + cre;
    };

    cout << cost_greedy(w, h) << "\n";
   // for(int i = 0; i < MV; ++i) {
   //     for(int j = 0; j < MV; ++j) {
   //         if(DP[i][j] == -1) continue;
   //         for(auto it : d) {
   //             if(j % it == 0 && i + it < MV)
   //                 improve(i + it, j, DP[i][j] + j / it);
   //             if(i % it == 0 && j + it < MV)
   //                 improve(i, j + it, DP[i][j] + i / it);
   //         }
   //         if(cost_greedy(i, j) != DP[i][j])
   //             cout << i << " " << j << " " << DP[i][j] << " | " << cost_greedy(i, j) << "\n";
   //     }
   // }
    return 0;
}