Advertisement
Anon2005

or

Apr 21st, 2023
771
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.68 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #pragma GCC optimize("Ofast")
  3. using namespace std;
  4.  
  5. const int val = (1 << 12);
  6.  
  7. char next_char()
  8. {
  9.     static char buff[val];
  10.     static int bp=val;
  11.     if(bp==val)
  12.     {
  13.         bp=0;
  14.         fread(buff,1,val,stdin);
  15.     }
  16.     return buff[bp++];
  17. }
  18. void get(int &a)
  19. {
  20.     a=0;
  21.     char ch;
  22.     do
  23.     {
  24.         ch=next_char();
  25.     }
  26.     while('0'>ch||ch>'9');
  27.     do
  28.     {
  29.         a=a*10+(ch-'0');
  30.         ch=next_char();
  31.     }
  32.     while('0'<=ch&&ch<='9');
  33. }
  34.  
  35. int rmq[9][9][501][501];
  36. int logue[501], v[501][501];
  37.  
  38. int sau(int x1, int y1, int x2, int y2)
  39. {
  40.     int l = logue[x2 - x1 + 1];
  41.     int c = logue[y2 - y1 + 1];
  42.     return (rmq[l][c][x2][y2] | rmq[l][c][x1 + (1 << l) - 1][y2] | rmq[l][c][x1 + (1 << l) - 1][y1 + (1 << c) - 1] | rmq[l][c][x2][y1 + (1 << c) - 1]);
  43. }
  44.  
  45. int main()
  46. {
  47.  
  48. #ifndef HOME
  49.     freopen("or.in", "r", stdin);
  50.     freopen("or.out", "w", stdout);
  51. #endif // HOME
  52. #ifdef HOME
  53.     freopen("test.in", "r", stdin);
  54.     freopen("test.out", "w", stdout);
  55. #endif // HOME
  56.     ios_base::sync_with_stdio(false);
  57.     int n, x;
  58.     get(x);
  59.     get(n);
  60.     for(int i = 1; i <= n; i++)
  61.         for(int j = 1; j <= n; j++)
  62.         {
  63.             get(v[i][j]);
  64.             rmq[0][0][i][j] = v[i][j];
  65.         }
  66.     for(int b = 1; (1 << b) <= n; b++)
  67.         for(int i = 1; i <= n; i++)
  68.             for(int j = (1 << b); j <= n; j++)
  69.                 rmq[0][b][i][j] = (rmq[0][b - 1][i][j] | rmq[0][b - 1][i][j - (1 << (b - 1))]);
  70.     for(int a = 1; (1 << a) <= n; a++)
  71.         for(int i = (1 << a); i <= n; i++)
  72.             for(int j = 1; j <= n; j++)
  73.                 rmq[a][0][i][j] = (rmq[a - 1][0][i][j] | rmq[a - 1][0][i - (1 << (a - 1))][j]);
  74.     for(int a = 1; (1 << a) <= n; a++)
  75.         for(int b = 1; (1 << b) <= n; b++)
  76.             for(int i = (1 << a); i <= n; i++)
  77.                 for(int j = (1 << b); j <= n; j++)
  78.                     rmq[a][b][i][j] = (rmq[a - 1][b - 1][i][j] | rmq[a - 1][b - 1][i - (1 << (a - 1))][j - (1 << (b - 1))] | rmq[a - 1][b - 1][i - (1 << (a - 1))][j] | rmq[a - 1][b - 1][i][j - (1 << (b - 1))]);
  79.     for(int i = 2; i <= n; i++)
  80.         logue[i] = 1 + logue[i / 2];
  81.     int minArea = n * n;
  82.     for(int l1 = 1; l1 <= n; l1++)
  83.         for(int l2 = l1; l2 <= n; l2++)
  84.         {
  85.             int st = 1;
  86.             for(int c = 1; c <= n; c++)
  87.             {
  88.                 while(st <= c && sau(l1, st, l2, c) >= x)
  89.                     st++;
  90.                 if(st > 1)
  91.                     st--;
  92.                 if(sau(l1, st, l2, c) == x)
  93.                     minArea = min(minArea, (l2 - l1 + 1) * (c - st + 1));
  94.             }
  95.         }
  96.     cout << minArea;
  97.     return 0;
  98. }
  99.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement