oj.uz

Submission #697238

# Submission time Handle Problem Language Result Execution time Memory
697238 2023-02-09T00:20:33 Z allllekssssa Bomb (IZhO17_bomb) C++14
50 / 100
 1000 ms 77372 KB 
#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 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 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< min(1, minW); i++) {
		for (int j = 0; j<min(5, minH); j++) {
           if (check(minW - i, minH -j)) ans = max(ans, (minW - i) * (minH -j));
		}
	}

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

	if (ans == 0) ans = 4;
	return ans;
}

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';
		}
	}
    
    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];
		}
	}

	if (n * m  * (n + m) >= 3e8) {
		cout << heuristic() << endl;
		return 0;
	}

   
    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;
}

Subtask #1
50.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 18 ms 30420 KB Output is correct
4 Correct 18 ms 30440 KB Output is correct
5 Correct 35 ms 340 KB Output is correct
6 Correct 6 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 0 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 0 ms 468 KB Output is correct
14 Correct 0 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 3 ms 1108 KB Output is correct
18 Correct 2 ms 1108 KB Output is correct
19 Correct 5 ms 1492 KB Output is correct
20 Correct 6 ms 1492 KB Output is correct
21 Correct 3 ms 980 KB Output is correct
22 Correct 5 ms 1236 KB Output is correct
23 Correct 8 ms 1620 KB Output is correct
24 Correct 4 ms 1364 KB Output is correct
25 Correct 9 ms 1620 KB Output is correct
26 Correct 8 ms 1620 KB Output is correct
27 Correct 134 ms 4764 KB Output is correct
28 Correct 241 ms 5076 KB Output is correct
29 Correct 319 ms 6444 KB Output is correct
30 Correct 612 ms 7684 KB Output is correct
31 Correct 482 ms 6076 KB Output is correct
32 Correct 478 ms 6996 KB Output is correct
33 Correct 786 ms 8084 KB Output is correct
34 Correct 120 ms 5580 KB Output is correct
35 Correct 583 ms 8084 KB Output is correct
36 Correct 681 ms 8084 KB Output is correct
37 Correct 0 ms 468 KB Output is correct
38 Correct 864 ms 76628 KB Output is correct
39 Correct 1 ms 556 KB Output is correct
40 Incorrect 93 ms 19840 KB Output isn't correct
41 Correct 1 ms 468 KB Output is correct
42 Correct 13 ms 1628 KB Output is correct
43 Correct 863 ms 76628 KB Output is correct
44 Execution timed out 1068 ms 8020 KB Time limit exceeded
45 Incorrect 680 ms 76620 KB Output isn't correct
46 Correct 845 ms 76632 KB Output is correct
47 Incorrect 686 ms 77260 KB Output isn't correct
48 Incorrect 700 ms 77280 KB Output isn't correct
49 Correct 885 ms 77364 KB Output is correct
50 Incorrect 697 ms 77352 KB Output isn't correct
51 Incorrect 651 ms 77360 KB Output isn't correct
52 Incorrect 641 ms 77360 KB Output isn't correct
53 Incorrect 629 ms 77360 KB Output isn't correct
54 Incorrect 633 ms 77364 KB Output isn't correct
55 Incorrect 625 ms 77372 KB Output isn't correct
56 Correct 919 ms 77296 KB Output is correct
57 Incorrect 709 ms 77232 KB Output isn't correct
58 Incorrect 782 ms 77228 KB Output isn't correct
59 Incorrect 689 ms 77236 KB Output isn't correct
60 Correct 815 ms 77240 KB Output is correct
61 Correct 846 ms 77188 KB Output is correct
62 Correct 876 ms 77220 KB Output is correct
63 Correct 815 ms 77228 KB Output is correct
64 Correct 746 ms 77256 KB Output is correct
65 Incorrect 644 ms 77232 KB Output isn't correct
66 Incorrect 624 ms 77216 KB Output isn't correct
67 Incorrect 659 ms 77140 KB Output isn't correct
68 Incorrect 610 ms 77140 KB Output isn't correct
69 Incorrect 687 ms 77240 KB Output isn't correct
70 Execution timed out 1037 ms 61796 KB Time limit exceeded
71 Incorrect 645 ms 77272 KB Output isn't correct
72 Incorrect 780 ms 77268 KB Output isn't correct
73 Incorrect 620 ms 77204 KB Output isn't correct
74 Incorrect 657 ms 77268 KB Output isn't correct
75 Incorrect 704 ms 77252 KB Output isn't correct
76 Incorrect 625 ms 77268 KB Output isn't correct
77 Incorrect 700 ms 77264 KB Output isn't correct
78 Incorrect 656 ms 77268 KB Output isn't correct
79 Incorrect 623 ms 77264 KB Output isn't correct
80 Incorrect 717 ms 77264 KB Output isn't correct
81 Incorrect 633 ms 77264 KB Output isn't correct
82 Incorrect 631 ms 77268 KB Output isn't correct
83 Incorrect 650 ms 77272 KB Output isn't correct
84 Incorrect 716 ms 77268 KB Output isn't correct
85 Incorrect 665 ms 77268 KB Output isn't correct
86 Incorrect 641 ms 77260 KB Output isn't correct
87 Incorrect 633 ms 77264 KB Output isn't correct
88 Incorrect 608 ms 77272 KB Output isn't correct
89 Incorrect 637 ms 77264 KB Output isn't correct
90 Execution timed out 1045 ms 61772 KB Time limit exceeded
91 Incorrect 641 ms 77136 KB Output isn't correct
92 Incorrect 623 ms 77044 KB Output isn't correct
93 Incorrect 616 ms 77136 KB Output isn't correct
94 Incorrect 621 ms 77140 KB Output isn't correct
95 Incorrect 631 ms 77140 KB Output isn't correct
96 Incorrect 629 ms 77216 KB Output isn't correct
97 Incorrect 614 ms 77140 KB Output isn't correct
98 Incorrect 626 ms 77136 KB Output isn't correct
99 Incorrect 638 ms 77140 KB Output isn't correct
100 Incorrect 627 ms 77144 KB Output isn't correct