Submission #697227

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
697227	2023-02-09T00:04:04 Z	allllekssssa	Bomb (IZhO17_bomb)	C++14	Compilation error	0 ms	0 KB

bomb

#include<bits/stdc++.h>

using namespace std;

const int maxN = 2600;
int n, m;
int a[maxN][maxN];
int d[maxN][maxN];
int c[maxN][maxN];
string s;

int heuristic() {
  
   int minW = n;
   int minH = m;

	for (int i = 1; i<=n; i++) {
		int cur = 0;
		for (int j = 1; j<=m; j++) {
			if (a[i][j] == 1) cur++; else {
				if (cur > 0) {
					minH = min(minH, cur);
					cur = 0;
				}
			}
		}

	   if (cur > 0) minH = min(minH, cur);
	}

	for (int j = 1; j<=m; j++) {
		int cur = 0;
		for (int i = 1; i<=n; i++) {
			if (a[i][j] == 1) cur++; else {
				if (cur > 0) {
					minW = min(minW, cur);
					cur = 0;
				}
			}
		}

		if (cur > 0) minW = min(minW, cur);
	}
    
    int ans = 0;
	for (int i = 0; i<minW; i++) {
		for (int j = 0; j<minH; j++) {
           if (check(minW - i, minH -j)) ans = max(ans, 1ll * 1ll(minW - i)* (minH -j))
		}
	}
	return ans;
}

int getDSum(int x1, int y1, int x2, int y2) {
	if (x2 > n || y2 > m) return 0;
	return d[x2][y2] + d[x1 - 1][y1 - 1] - d[x1 - 1][y2] - d[x2][y1 - 1];
}

int getCSum(int x1, int y1, int x2, int y2) {
	x1 = max(x1, 1);
	y1 = max(y1, 1);
	return c[x2][y2] + c[x1 - 1][y1 - 1] - c[x1 - 1][y2] - c[x2][y1 - 1];
}

bool check(int x, int y) {

	for (int i = 1; i<=n; i++) {
		for (int j = 1; j<=m; j++) {
			c[i][j] = 0;
		}
	}
   
   for (int i = 1; i<=n; i++) {
   	 for (int j = 1; j<=m; j++) {
   	 	if (getDSum(i, j, i + x - 1, j + y - 1) == x * y) c[i][j] = 1;
   	 }
   }

   for (int i = 1; i <= n; i++) {
		for (int j = 1; j<=m; j++) {
			c[i][j] += c[i - 1][j] + c[i][j - 1] - c[i - 1][j - 1];
		}
	}

   for (int i = 1; i<=n; i++) {
   	for (int j = 1; j <= m; j++) {
 		  if (a[i][j] && getCSum(i - x + 1, j - y + 1, i, j) == 0) return false;
   	  }
   }

   return true;
}

int main() {

	cin >> n >> m;

	for (int i = 1; i <=n; i++) {
		cin >> s;

		for (int j = 0; j < m; j++) {
			a[i][j + 1] = s[j] - '0';
		}
	}

	if (n >= 500 || m >= 500) {
		cout << heuristic() << endl;
		return 0;
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j<=m; j++) {
			d[i][j] = d[i - 1][j] + d[i][j - 1] + a[i][j] - d[i - 1][j - 1];
		}
	}
   
    int ans = 0;
    
    int width = m;
	for (int i = 1; i <=n; i++) {

		while (width > 0 && !check(i, width)) width--;

		ans = max(ans, i * width);
	}
    
    cout << ans << endl;
}

Compilation message

bomb.cpp: In function 'int heuristic()':
bomb.cpp:48:16: error: 'check' was not declared in this scope
   48 |            if (check(minW - i, minH -j)) ans = max(ans, 1ll * 1ll(minW - i)* (minH -j))
      |                ^~~~~
bomb.cpp:48:75: error: expression cannot be used as a function
   48 |            if (check(minW - i, minH -j)) ans = max(ans, 1ll * 1ll(minW - i)* (minH -j))
      |                                                                           ^