oj.uz

답안 #697234

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
697234 2023-02-09T00:13:35 Z allllekssssa Bomb (IZhO17_bomb) C++14
41 / 100
 1000 ms 77244 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(4, minW); i++) {
		for (int j = 0; j<min(4, minH); j++) {
           if (check(minW - i, minH -j)) ans = max(ans, (minW - i) * (minH -j));
		}
	}
	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
41.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 17 ms 30420 KB Output is correct
4 Correct 19 ms 30440 KB Output is correct
5 Correct 37 ms 340 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 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 0 ms 468 KB Output is correct
13 Correct 0 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 0 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 4 ms 980 KB Output is correct
22 Correct 7 ms 1312 KB Output is correct
23 Correct 9 ms 1620 KB Output is correct
24 Correct 5 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 125 ms 4768 KB Output is correct
28 Correct 249 ms 5076 KB Output is correct
29 Correct 343 ms 6452 KB Output is correct
30 Correct 620 ms 7684 KB Output is correct
31 Correct 466 ms 6076 KB Output is correct
32 Correct 491 ms 6996 KB Output is correct
33 Correct 748 ms 8084 KB Output is correct
34 Correct 112 ms 5516 KB Output is correct
35 Correct 555 ms 8084 KB Output is correct
36 Correct 664 ms 8084 KB Output is correct
37 Correct 0 ms 468 KB Output is correct
38 Execution timed out 1086 ms 76536 KB Time limit exceeded
39 Correct 1 ms 468 KB Output is correct
40 Incorrect 116 ms 19868 KB Output isn't correct
41 Correct 1 ms 468 KB Output is correct
42 Correct 11 ms 1628 KB Output is correct
43 Execution timed out 1048 ms 76824 KB Time limit exceeded
44 Correct 917 ms 8080 KB Output is correct
45 Incorrect 804 ms 76628 KB Output isn't correct
46 Execution timed out 1036 ms 76712 KB Time limit exceeded
47 Incorrect 792 ms 76564 KB Output isn't correct
48 Incorrect 834 ms 76700 KB Output isn't correct
49 Execution timed out 1089 ms 76640 KB Time limit exceeded
50 Incorrect 829 ms 76624 KB Output isn't correct
51 Incorrect 824 ms 76748 KB Output isn't correct
52 Incorrect 823 ms 76660 KB Output isn't correct
53 Incorrect 853 ms 76628 KB Output isn't correct
54 Incorrect 830 ms 76620 KB Output isn't correct
55 Incorrect 840 ms 76560 KB Output isn't correct
56 Execution timed out 1062 ms 76528 KB Time limit exceeded
57 Incorrect 986 ms 76624 KB Output isn't correct
58 Incorrect 919 ms 76620 KB Output isn't correct
59 Incorrect 915 ms 76744 KB Output isn't correct
60 Execution timed out 1033 ms 76628 KB Time limit exceeded
61 Execution timed out 1096 ms 76620 KB Time limit exceeded
62 Execution timed out 1041 ms 77152 KB Time limit exceeded
63 Execution timed out 1052 ms 77092 KB Time limit exceeded
64 Execution timed out 1014 ms 77144 KB Time limit exceeded
65 Incorrect 878 ms 77140 KB Output isn't correct
66 Incorrect 868 ms 77140 KB Output isn't correct
67 Incorrect 867 ms 77112 KB Output isn't correct
68 Incorrect 861 ms 77100 KB Output isn't correct
69 Incorrect 963 ms 77144 KB Output isn't correct
70 Execution timed out 1008 ms 61652 KB Time limit exceeded
71 Incorrect 879 ms 77136 KB Output isn't correct
72 Incorrect 857 ms 77136 KB Output isn't correct
73 Incorrect 854 ms 77120 KB Output isn't correct
74 Incorrect 886 ms 77244 KB Output isn't correct
75 Incorrect 857 ms 77140 KB Output isn't correct
76 Incorrect 869 ms 77040 KB Output isn't correct
77 Incorrect 865 ms 77140 KB Output isn't correct
78 Incorrect 889 ms 77144 KB Output isn't correct
79 Incorrect 851 ms 77140 KB Output isn't correct
80 Incorrect 850 ms 77088 KB Output isn't correct
81 Incorrect 902 ms 77144 KB Output isn't correct
82 Incorrect 886 ms 77140 KB Output isn't correct
83 Incorrect 892 ms 77140 KB Output isn't correct
84 Incorrect 860 ms 77136 KB Output isn't correct
85 Incorrect 839 ms 77136 KB Output isn't correct
86 Incorrect 858 ms 77132 KB Output isn't correct
87 Incorrect 858 ms 77140 KB Output isn't correct
88 Incorrect 842 ms 77140 KB Output isn't correct
89 Incorrect 853 ms 77140 KB Output isn't correct
90 Execution timed out 1062 ms 61648 KB Time limit exceeded
91 Incorrect 874 ms 77044 KB Output isn't correct
92 Execution timed out 1008 ms 77012 KB Time limit exceeded
93 Incorrect 866 ms 77012 KB Output isn't correct
94 Incorrect 840 ms 77016 KB Output isn't correct
95 Incorrect 881 ms 77016 KB Output isn't correct
96 Incorrect 849 ms 77012 KB Output isn't correct
97 Incorrect 856 ms 77036 KB Output isn't correct
98 Incorrect 953 ms 76936 KB Output isn't correct
99 Incorrect 912 ms 77012 KB Output isn't correct
100 Incorrect 998 ms 77024 KB Output isn't correct