#include <bits/stdc++.h> using namespace std; void __print(int x) {cerr << x;} void __print(long x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(unsigned x) {cerr << x;} void __print(unsigned long x) {cerr << x;} void __print(unsigned long long x) {cerr << x;} void __print(float x) {cerr << x;} void __print(double x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << '\'' << x << '\'';} void __print(const char *x) {cerr << '\"' << x << '\"';} void __print(const string &x) {cerr << '\"' << x << '\"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifndef ONLINE_JUDGE #define debug(x...) cerr << "[" << #x << "] = ["; _print(x) #else #define debug(x...) #endif #define int long long using ll = long long; constexpr int MAXN = 1e6 + 7; constexpr int oo = 1e9 + 7; // each of the recursive calls wants to calculate the ans for the rectangle // described by points (i, j) and (i_, j_) bool ok; int solve(int i, int j, int i_, int j_, int k, vector<int> &a, int n) { if (i == i_ || j == j_) { return 0; } if (k >= n) { // nothing fits and there are still tiles unfilled! bad situation ok = false; return 0; } if (a[k] == 1) return (i_ - i) * (j_ - j); else { // let's firstly check how many can we put vertically, // then horizontally and invoke another recursive calls with k + 1 // edge case: we can't put a single one so we just invoke with k + 1 if (i + a[k] > i_ || j + a[k] > j_) { if (k == n - 1) { // we cant lessen the square size anymore ok = false; return 0; } else { // just try again with smaller square solve(i, j, i_, j_, k + 1, a, n); } } else { // we can put at least one so we try to calculate the max # int vertically = (i_ - i) / a[k]; int horizontally = (j_ - j) / a[k]; pair<int, int> p1, p2, p3, p1_, p2_, p3_; p1 = {i + vertically * a[k], j}; p2 = {i, j + horizontally * a[k]}; p3 = {i + vertically * a[k], j + horizontally * a[k]}; p1_ = {i_, j + horizontally * a[k]}; p2_ = {i + vertically * a[k], j_}; p3_ = {i_, j_}; return vertically * horizontally + solve(p1.first, p1.second, p1_.first, p1_.second, k + 1, a, n) + solve(p2.first, p2.second, p2_.first, p2_.second, k + 1, a, n) + solve(p3.first, p3.second, p3_.first, p3_.second, k + 1, a, n); } } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int h, w; cin >> h >> w; int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } reverse(a.begin(), a.end()); ok = true; int ans = solve(0, 0, h, w, 0, a, n); cout << (ok ? ans : -1) << '\n'; }
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 96 97 98 99 100 101 102 103 | #include <bits/stdc++.h> using namespace std; void __print(int x) {cerr << x;} void __print(long x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(unsigned x) {cerr << x;} void __print(unsigned long x) {cerr << x;} void __print(unsigned long long x) {cerr << x;} void __print(float x) {cerr << x;} void __print(double x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << '\'' << x << '\'';} void __print(const char *x) {cerr << '\"' << x << '\"';} void __print(const string &x) {cerr << '\"' << x << '\"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifndef ONLINE_JUDGE #define debug(x...) cerr << "[" << #x << "] = ["; _print(x) #else #define debug(x...) #endif #define int long long using ll = long long; constexpr int MAXN = 1e6 + 7; constexpr int oo = 1e9 + 7; // each of the recursive calls wants to calculate the ans for the rectangle // described by points (i, j) and (i_, j_) bool ok; int solve(int i, int j, int i_, int j_, int k, vector<int> &a, int n) { if (i == i_ || j == j_) { return 0; } if (k >= n) { // nothing fits and there are still tiles unfilled! bad situation ok = false; return 0; } if (a[k] == 1) return (i_ - i) * (j_ - j); else { // let's firstly check how many can we put vertically, // then horizontally and invoke another recursive calls with k + 1 // edge case: we can't put a single one so we just invoke with k + 1 if (i + a[k] > i_ || j + a[k] > j_) { if (k == n - 1) { // we cant lessen the square size anymore ok = false; return 0; } else { // just try again with smaller square solve(i, j, i_, j_, k + 1, a, n); } } else { // we can put at least one so we try to calculate the max # int vertically = (i_ - i) / a[k]; int horizontally = (j_ - j) / a[k]; pair<int, int> p1, p2, p3, p1_, p2_, p3_; p1 = {i + vertically * a[k], j}; p2 = {i, j + horizontally * a[k]}; p3 = {i + vertically * a[k], j + horizontally * a[k]}; p1_ = {i_, j + horizontally * a[k]}; p2_ = {i + vertically * a[k], j_}; p3_ = {i_, j_}; return vertically * horizontally + solve(p1.first, p1.second, p1_.first, p1_.second, k + 1, a, n) + solve(p2.first, p2.second, p2_.first, p2_.second, k + 1, a, n) + solve(p3.first, p3.second, p3_.first, p3_.second, k + 1, a, n); } } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int h, w; cin >> h >> w; int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } reverse(a.begin(), a.end()); ok = true; int ans = solve(0, 0, h, w, 0, a, n); cout << (ok ? ans : -1) << '\n'; } |