#include <iostream> #include <algorithm> #include <stack> using namespace std; long long int H, W; const int MAX_N = 31; long long int D[MAX_N]; int N; pair<long long int, long long int> mp(long long int a, long long int b) { return make_pair( min(a, b), max(a, b)); } int find(long long int size) { for (int i = N - 1; i >= 0; i--) { if (D[i] <= size) { return D[i]; } } return -1; } long long int licz() { stack<pair<long long int, long long int>> stos; long long int cnt = 0; stos.push(mp(H, W)); while (!stos.empty()) { pair<int, int> next = stos.top(); stos.pop(); long long int h = next.first; long long int w = next.second; long long int d = find(h); if (d == -1) return -1; cnt += (h / d) * (w / d); long long int h1 = h % d; long long int w1 = d * (w/d); if (h1 != 0 && w1 != 0) { stos.push(mp(h1, w1)); } long long int w2 = w % d; if (h != 0 && w2 != 0) { stos.push(mp(h, w2)); } } return cnt; } int main() { cin >> H >> W >> N; for (int i = 0; i < N; i++) { cin >> D[i]; } cout << licz() << endl; return 0; }
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 | #include <iostream> #include <algorithm> #include <stack> using namespace std; long long int H, W; const int MAX_N = 31; long long int D[MAX_N]; int N; pair<long long int, long long int> mp(long long int a, long long int b) { return make_pair( min(a, b), max(a, b)); } int find(long long int size) { for (int i = N - 1; i >= 0; i--) { if (D[i] <= size) { return D[i]; } } return -1; } long long int licz() { stack<pair<long long int, long long int>> stos; long long int cnt = 0; stos.push(mp(H, W)); while (!stos.empty()) { pair<int, int> next = stos.top(); stos.pop(); long long int h = next.first; long long int w = next.second; long long int d = find(h); if (d == -1) return -1; cnt += (h / d) * (w / d); long long int h1 = h % d; long long int w1 = d * (w/d); if (h1 != 0 && w1 != 0) { stos.push(mp(h1, w1)); } long long int w2 = w % d; if (h != 0 && w2 != 0) { stos.push(mp(h, w2)); } } return cnt; } int main() { cin >> H >> W >> N; for (int i = 0; i < N; i++) { cin >> D[i]; } cout << licz() << endl; return 0; } |