oj.uz

Submission #697259

# Submission time Handle Problem Language Result Execution time Memory
697259 2023-02-09T01:24:10 Z allllekssssa Bomb (IZhO17_bomb) C++14
52 / 100
 958 ms 51356 KB 
#include<bits/stdc++.h>
 
using namespace std;


#define pii pair<int ,int>
#define pb push_back

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

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 heuristic1() {
    
	vector<pii> gornji;

	for (int i = 1; i<=n; i++) {
		for (int j = 1; j<=m; j++) {
			if (a[i - 1][j] == 0 && a[i][j - 1] == 0 && a[i][j] == 1) gornji.pb({i, j});
		}
	}

	random_shuffle(gornji.begin(), gornji.end());
    
    for (int i = 1; i <=n; i++) {
    	cnt[i] = m;
    }

    for (int i = 0; i < min(900, (int) gornji.size()); i++) {
       for (int len = 1; len <= n; len++) {
          
          int x = gornji[i].first;
          int y = gornji[i].second;

       	  int lo = -1;
       	  int ro = m + 1;
 
       	  while(lo < ro - 1) {
       	  	 int mid = lo + ro >> 1;
       	  	 if (getDSum(x, y, x + len - 1, y + mid - 1) == len * mid) lo = mid; else ro = mid;
       	  }

       	  cnt[len] = min(cnt[len], lo);
       }
    }


    int ans = 0;
    for (int i = 1; i<=n; i++) {
    	ans = max(ans, i * cnt[i]);
    }

    return ans;
}
 
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 = minW * minH;
    if (!check(minW, minH)) return heuristic1();
	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 > 450 || m > 450) {
		cout << heuristic1() << 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;
}

Compilation message

bomb.cpp: In function 'int heuristic1()':
bomb.cpp:83:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |             int mid = lo + ro >> 1;
      |                       ~~~^~~~

Subtask #1
52.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 10 ms 20308 KB Output is correct
4 Correct 17 ms 20384 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 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 1 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 1 ms 468 KB Output is correct
14 Correct 1 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 3 ms 1108 KB Output is correct
19 Correct 6 ms 1532 KB Output is correct
20 Correct 8 ms 1492 KB Output is correct
21 Correct 4 ms 980 KB Output is correct
22 Correct 5 ms 1236 KB Output is correct
23 Correct 9 ms 1632 KB Output is correct
24 Correct 4 ms 1364 KB Output is correct
25 Correct 9 ms 1636 KB Output is correct
26 Correct 9 ms 1620 KB Output is correct
27 Correct 162 ms 4692 KB Output is correct
28 Correct 257 ms 5076 KB Output is correct
29 Correct 378 ms 6456 KB Output is correct
30 Correct 662 ms 7700 KB Output is correct
31 Correct 491 ms 6080 KB Output is correct
32 Correct 493 ms 6996 KB Output is correct
33 Correct 789 ms 8088 KB Output is correct
34 Correct 117 ms 5460 KB Output is correct
35 Correct 575 ms 8092 KB Output is correct
36 Correct 676 ms 8088 KB Output is correct
37 Correct 1 ms 468 KB Output is correct
38 Correct 181 ms 51084 KB Output is correct
39 Correct 1 ms 468 KB Output is correct
40 Incorrect 31 ms 13320 KB Output isn't correct
41 Correct 1 ms 468 KB Output is correct
42 Correct 12 ms 1632 KB Output is correct
43 Incorrect 390 ms 51204 KB Output isn't correct
44 Correct 958 ms 8088 KB Output is correct
45 Incorrect 307 ms 51148 KB Output isn't correct
46 Correct 347 ms 51232 KB Output is correct
47 Incorrect 354 ms 51200 KB Output isn't correct
48 Correct 207 ms 51108 KB Output is correct
49 Incorrect 189 ms 51152 KB Output isn't correct
50 Incorrect 221 ms 51240 KB Output isn't correct
51 Incorrect 208 ms 51160 KB Output isn't correct
52 Correct 220 ms 51184 KB Output is correct
53 Incorrect 204 ms 51156 KB Output isn't correct
54 Correct 269 ms 51204 KB Output is correct
55 Incorrect 252 ms 51204 KB Output isn't correct
56 Correct 215 ms 51296 KB Output is correct
57 Incorrect 180 ms 51192 KB Output isn't correct
58 Correct 208 ms 51196 KB Output is correct
59 Correct 218 ms 51200 KB Output is correct
60 Incorrect 165 ms 51076 KB Output isn't correct
61 Incorrect 163 ms 51100 KB Output isn't correct
62 Incorrect 173 ms 51120 KB Output isn't correct
63 Incorrect 166 ms 51120 KB Output isn't correct
64 Incorrect 166 ms 51168 KB Output isn't correct
65 Correct 204 ms 51188 KB Output is correct
66 Incorrect 175 ms 51156 KB Output isn't correct
67 Correct 211 ms 51108 KB Output is correct
68 Incorrect 207 ms 51192 KB Output isn't correct
69 Correct 180 ms 51172 KB Output is correct
70 Incorrect 116 ms 41036 KB Output isn't correct
71 Incorrect 171 ms 51076 KB Output isn't correct
72 Incorrect 179 ms 51148 KB Output isn't correct
73 Incorrect 167 ms 51276 KB Output isn't correct
74 Incorrect 171 ms 51152 KB Output isn't correct
75 Incorrect 183 ms 51120 KB Output isn't correct
76 Incorrect 165 ms 51156 KB Output isn't correct
77 Incorrect 166 ms 51244 KB Output isn't correct
78 Incorrect 169 ms 51196 KB Output isn't correct
79 Incorrect 166 ms 51196 KB Output isn't correct
80 Incorrect 174 ms 51248 KB Output isn't correct
81 Incorrect 173 ms 51276 KB Output isn't correct
82 Incorrect 166 ms 51148 KB Output isn't correct
83 Incorrect 164 ms 51112 KB Output isn't correct
84 Incorrect 164 ms 51172 KB Output isn't correct
85 Incorrect 165 ms 51124 KB Output isn't correct
86 Incorrect 163 ms 51148 KB Output isn't correct
87 Incorrect 165 ms 51092 KB Output isn't correct
88 Incorrect 176 ms 51100 KB Output isn't correct
89 Incorrect 165 ms 51200 KB Output isn't correct
90 Incorrect 114 ms 40928 KB Output isn't correct
91 Incorrect 166 ms 51176 KB Output isn't correct
92 Incorrect 172 ms 51256 KB Output isn't correct
93 Incorrect 166 ms 51148 KB Output isn't correct
94 Incorrect 164 ms 51184 KB Output isn't correct
95 Incorrect 165 ms 51148 KB Output isn't correct
96 Incorrect 167 ms 51356 KB Output isn't correct
97 Incorrect 167 ms 51196 KB Output isn't correct
98 Incorrect 181 ms 51104 KB Output isn't correct
99 Incorrect 167 ms 51180 KB Output isn't correct
100 Incorrect 168 ms 51184 KB Output isn't correct