Advertisement
Guest User

Untitled

a guest
Nov 22nd, 2019
148
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.58 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int MAX_SIZE = 100;
  4. unsigned char field[MAX_SIZE+2][MAX_SIZE+2] = {};
  5. int prefix[MAX_SIZE+2][MAX_SIZE+2] = {};
  6.  
  7. int sum(int i1, int j1, int i2, int j2)
  8. {
  9.   return prefix[i2][j2] - prefix[i1-1][j2] - prefix[i2][j1-1] + prefix[i1-1][j1-1];
  10. }
  11.  
  12. void fill_field(int i1, int j1, int i2, int j2)
  13. {
  14.   for (int i = i1-1; i <= i2+1; ++i)
  15.     for (int j = j1-1; j <= j2+1; ++j)
  16.       field[i][j] = 1;
  17. }
  18.  
  19. int main()
  20. {
  21.   ios_base::sync_with_stdio(0);
  22.   cin.tie(0);
  23.   freopen("INPUT.TXT", "r", stdin);
  24.   int n, m, k;
  25.   cin >> n >> m >> k;
  26.  
  27.   for (int i=0; i<n+2; ++i)
  28.   {
  29.     field[i][0] = field[i][m+1] = 1;
  30.     prefix[i][0] = i + 1;
  31.   }
  32.   for (int j=0; j<m+2; ++j)
  33.   {
  34.     field[0][j] = field[n+1][j] = 1;
  35.     prefix[0][j] = j + 1;
  36.   }
  37.  
  38.   for(int i=0; i<k; ++i)
  39.   {
  40.     int i1, i2, j1, j2;
  41.     cin >> i1 >> j1 >> i2 >> j2;
  42.     fill_field(i1, j1, i2, j2);
  43.   }
  44.  
  45.   for(int i = 1; i < n+1; ++i)
  46.     for(int j = 1; j < m+1; ++j)
  47.         prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + field[i][j];
  48.  
  49.   int square = 0;
  50.   for(int w = m; w > 1; --w)
  51.   {
  52.     bool found = false;
  53.     for(int h = n; h > 1 && !found;  --h)
  54.     {
  55.       for(int i = 1; i + h < n + 2 && !found; ++i)
  56.       {
  57.         for(int j = 1; j + w < m + 2 && !found; ++j)
  58.         {
  59.           if ( sum(i, j, i+h-1, j+w-1) == 0 )
  60.           {
  61.             if (w * h > square)
  62.             {
  63.               square = w * h;
  64.               found = true;
  65.             }
  66.           }
  67.         }
  68.       }
  69.     }
  70.   }
  71.  
  72.   cout << square;
  73.   return 0;
  74. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement