fork(1) download
copy 
  1.     #include <bits/stdc++.h> 
  2.  
  3.     using namespace std;
  4.  
  5.     const int MaxN = (int)2e2 + 10;
  6.     const int INF = (int)1e9;
  7.     const int MOD = 998244353;
  8.  
  9.     int n, m;
  10.     char s[MaxN][MaxN];
  11.     int sums[2][MaxN][MaxN];
  12.     int dp[MaxN * MaxN];
  13.  
  14.     int get(int sum[MaxN][MaxN], int xl, int yl, int xr, int yr) {
  15.     	return sum[xr][yr] - sum[xl - 1][yr] - sum[xr][yl - 1] + sum[xl - 1][yl - 1];
  16.     }
  17.  
  18.     int main() {
  19.     //	freopen("input.txt", "r", stdin);
  20.     	scanf("%d%d\n", &n, &m);
  21.     	for (int i = 1; i <= n; ++i) {
  22.     		scanf("%s", s[i] + 1);
  23.     		for (int j = 1; j <= m; ++j) {
  24.     			if ((i + j) % 2 == 0) {
  25.     				sums[0][i][j] = (s[i][j] == '1');
  26.     				sums[1][i][j] = (s[i][j] == '0');
  27.     			} else {
  28.     				sums[0][i][j] = (s[i][j] == '0');
  29.     				sums[1][i][j] = (s[i][j] == '1');
  30.     			}
  31.     			for (int k = 0; k < 2; ++k) {
  32.     				sums[k][i][j] += sums[k][i - 1][j];
  33.     				sums[k][i][j] += sums[k][i][j - 1];
  34.     				sums[k][i][j] -= sums[k][i - 1][j - 1];
  35.     			}
  36.     		}
  37.     	}
  38.     	for (int x = 1; x <= n; ++x) {
  39.     		for (int y = 1; y <= m; ++y) {
  40.     			for (int d = 1; x + d - 1 <= n && y + d - 1 <= m; ++d) {
  41.     				{
  42.     					int cor = get(sums[0], x, y, x + d - 1, y + d - 1);
  43.     					dp[d * d - cor] = max(dp[d * d - cor], d);
  44.     				}
  45.     				{
  46.     					int cor = get(sums[1], x, y, x + d - 1, y + d - 1);
  47.     					dp[d * d - cor] = max(dp[d * d - cor], d);
  48.     				}
  49.     			}
  50.     		}
  51.     	}
  52.     	for (int i = 1; i <= n * m; ++i) {
  53.     		dp[i] = max(dp[i], dp[i - 1]);
  54.     	}
  55.     	int t;
  56.     	scanf("%d", &t);
  57.     	while (t --> 0) {
  58.     		int ti;
  59.     		scanf("%d", &ti);
  60.     		if (ti > n * m) {
  61.     			ti = n * m;
  62.     		}
  63.     		printf("%d\n", dp[ti]);
  64.     	}
  65.     	return 0;
  66.     }
  67.  
Success #stdin #stdout 0s 15792KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rBuR7I
language:
C++14 (gcc 8.3)
created:
5 years 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!