Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #pragma GCC optimize("Ofast")
- using namespace std;
- const int val = (1 << 12);
- char next_char()
- {
- static char buff[val];
- static int bp=val;
- if(bp==val)
- {
- bp=0;
- fread(buff,1,val,stdin);
- }
- return buff[bp++];
- }
- void get(int &a)
- {
- a=0;
- char ch;
- do
- {
- ch=next_char();
- }
- while('0'>ch||ch>'9');
- do
- {
- a=a*10+(ch-'0');
- ch=next_char();
- }
- while('0'<=ch&&ch<='9');
- }
- int rmq[9][9][501][501];
- int logue[501], v[501][501];
- int sau(int x1, int y1, int x2, int y2)
- {
- int l = logue[x2 - x1 + 1];
- int c = logue[y2 - y1 + 1];
- 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]);
- }
- int main()
- {
- #ifndef HOME
- freopen("or.in", "r", stdin);
- freopen("or.out", "w", stdout);
- #endif // HOME
- #ifdef HOME
- freopen("test.in", "r", stdin);
- freopen("test.out", "w", stdout);
- #endif // HOME
- ios_base::sync_with_stdio(false);
- int n, x;
- get(x);
- get(n);
- for(int i = 1; i <= n; i++)
- for(int j = 1; j <= n; j++)
- {
- get(v[i][j]);
- rmq[0][0][i][j] = v[i][j];
- }
- for(int b = 1; (1 << b) <= n; b++)
- for(int i = 1; i <= n; i++)
- for(int j = (1 << b); j <= n; j++)
- rmq[0][b][i][j] = (rmq[0][b - 1][i][j] | rmq[0][b - 1][i][j - (1 << (b - 1))]);
- for(int a = 1; (1 << a) <= n; a++)
- for(int i = (1 << a); i <= n; i++)
- for(int j = 1; j <= n; j++)
- rmq[a][0][i][j] = (rmq[a - 1][0][i][j] | rmq[a - 1][0][i - (1 << (a - 1))][j]);
- for(int a = 1; (1 << a) <= n; a++)
- for(int b = 1; (1 << b) <= n; b++)
- for(int i = (1 << a); i <= n; i++)
- for(int j = (1 << b); j <= n; j++)
- 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))]);
- for(int i = 2; i <= n; i++)
- logue[i] = 1 + logue[i / 2];
- int minArea = n * n;
- for(int l1 = 1; l1 <= n; l1++)
- for(int l2 = l1; l2 <= n; l2++)
- {
- int st = 1;
- for(int c = 1; c <= n; c++)
- {
- while(st <= c && sau(l1, st, l2, c) >= x)
- st++;
- if(st > 1)
- st--;
- if(sau(l1, st, l2, c) == x)
- minArea = min(minArea, (l2 - l1 + 1) * (c - st + 1));
- }
- }
- cout << minArea;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement