#include <algorithm> #include <iostream> #include <cstdio> #include <cstdlib> #include <vector> int c; #define SKIP_WHITESPACE \ { \ while (1) { \ c = fgetc(stdin); \ if (c != ' ' && c != '\n' && c != '\r') \ break; \ } \ } \ #define READ_INT \ ({ \ SKIP_WHITESPACE \ int ret = c - '0'; \ while (1) { \ c = fgetc(stdin); \ if (c < '0' || c > '9') \ break; \ ret = ret * 10 + c - '0'; \ } \ ret; \ }) \ int pics[30]; struct task { int h; int w; int k; }; int main(int argc, char* argv[]) { std::ios_base::sync_with_stdio (false); uint64_t sum = 0; int n, h, w; h = READ_INT; w = READ_INT; n = READ_INT; int i, d, k, p, q; for (i = 0; i < n; ++i) { d = READ_INT; pics[i] = d; } std::vector<task> tasks; int a = (h < w) ? h : w; int b = (h > w) ? h : w; tasks.emplace_back(task{a, b, n - 1}); while (!tasks.empty()) { a = tasks.back().h; b = tasks.back().w; k = tasks.back().k; tasks.pop_back(); while (k >= 0) { d = pics[k]; if (a / d > 0) { break; } k--; } if (k < 0) { std::cout << "-1\n"; return EXIT_SUCCESS; } p = a / d; q = b / d; sum += uint64_t(p) * uint64_t(q); if (a % d) tasks.emplace_back(task{a % d, b, k - 1}); h = p * d; w = b % d; if (b % d) { a = (h < w) ? h : w; b = (h > w) ? h : w; tasks.emplace_back(task{a, b, k - 1}); } } std::cout << sum << "\n"; return EXIT_SUCCESS; }
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 87 88 89 90 91 92 93 94 95 | #include <algorithm> #include <iostream> #include <cstdio> #include <cstdlib> #include <vector> int c; #define SKIP_WHITESPACE \ { \ while (1) { \ c = fgetc(stdin); \ if (c != ' ' && c != '\n' && c != '\r') \ break; \ } \ } \ #define READ_INT \ ({ \ SKIP_WHITESPACE \ int ret = c - '0'; \ while (1) { \ c = fgetc(stdin); \ if (c < '0' || c > '9') \ break; \ ret = ret * 10 + c - '0'; \ } \ ret; \ }) \ int pics[30]; struct task { int h; int w; int k; }; int main(int argc, char* argv[]) { std::ios_base::sync_with_stdio (false); uint64_t sum = 0; int n, h, w; h = READ_INT; w = READ_INT; n = READ_INT; int i, d, k, p, q; for (i = 0; i < n; ++i) { d = READ_INT; pics[i] = d; } std::vector<task> tasks; int a = (h < w) ? h : w; int b = (h > w) ? h : w; tasks.emplace_back(task{a, b, n - 1}); while (!tasks.empty()) { a = tasks.back().h; b = tasks.back().w; k = tasks.back().k; tasks.pop_back(); while (k >= 0) { d = pics[k]; if (a / d > 0) { break; } k--; } if (k < 0) { std::cout << "-1\n"; return EXIT_SUCCESS; } p = a / d; q = b / d; sum += uint64_t(p) * uint64_t(q); if (a % d) tasks.emplace_back(task{a % d, b, k - 1}); h = p * d; w = b % d; if (b % d) { a = (h < w) ? h : w; b = (h > w) ? h : w; tasks.emplace_back(task{a, b, k - 1}); } } std::cout << sum << "\n"; return EXIT_SUCCESS; } |