oj.uz

Submission #697247

# Submission time Handle Problem Language Result Execution time Memory
697247 2023-02-09T01:13:11 Z allllekssssa Bomb (IZhO17_bomb) C++14
42 / 100
 1000 ms 117864 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) 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(200, (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 + i - 1, y + mid - 1) == i * 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 * m  * (n + m) >= 3e8) {
		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
42.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 568 KB Output is correct
3 Correct 19 ms 30456 KB Output is correct
4 Correct 18 ms 30420 KB Output is correct
5 Correct 39 ms 348 KB Output is correct
6 Correct 7 ms 340 KB Output is correct
7 Correct 1 ms 312 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 7 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 5 ms 1236 KB Output is correct
23 Correct 9 ms 1600 KB Output is correct
24 Correct 5 ms 1364 KB Output is correct
25 Correct 10 ms 1620 KB Output is correct
26 Correct 11 ms 1644 KB Output is correct
27 Correct 155 ms 4852 KB Output is correct
28 Correct 266 ms 5204 KB Output is correct
29 Correct 338 ms 6572 KB Output is correct
30 Correct 655 ms 7828 KB Output is correct
31 Correct 554 ms 6204 KB Output is correct
32 Correct 492 ms 7124 KB Output is correct
33 Correct 793 ms 8268 KB Output is correct
34 Correct 139 ms 5608 KB Output is correct
35 Correct 606 ms 8224 KB Output is correct
36 Correct 696 ms 8228 KB Output is correct
37 Correct 1 ms 468 KB Output is correct
38 Correct 171 ms 51980 KB Output is correct
39 Correct 1 ms 568 KB Output is correct
40 Incorrect 25 ms 13660 KB Output isn't correct
41 Correct 1 ms 468 KB Output is correct
42 Correct 15 ms 1620 KB Output is correct
43 Incorrect 263 ms 68460 KB Output isn't correct
44 Execution timed out 1012 ms 8216 KB Time limit exceeded
45 Incorrect 287 ms 84888 KB Output isn't correct
46 Incorrect 314 ms 84904 KB Output isn't correct
47 Incorrect 291 ms 84864 KB Output isn't correct
48 Incorrect 311 ms 85032 KB Output isn't correct
49 Incorrect 172 ms 51904 KB Output isn't correct
50 Incorrect 299 ms 84904 KB Output isn't correct
51 Incorrect 295 ms 84852 KB Output isn't correct
52 Incorrect 298 ms 84908 KB Output isn't correct
53 Incorrect 335 ms 84852 KB Output isn't correct
54 Incorrect 397 ms 117728 KB Output isn't correct
55 Incorrect 412 ms 117768 KB Output isn't correct
56 Correct 170 ms 51912 KB Output is correct
57 Incorrect 444 ms 117568 KB Output isn't correct
58 Incorrect 419 ms 117556 KB Output isn't correct
59 Incorrect 434 ms 117612 KB Output isn't correct
60 Incorrect 320 ms 85060 KB Output isn't correct
61 Incorrect 168 ms 51760 KB Output isn't correct
62 Incorrect 164 ms 51736 KB Output isn't correct
63 Incorrect 173 ms 51944 KB Output isn't correct
64 Incorrect 402 ms 117616 KB Output isn't correct
65 Incorrect 305 ms 84812 KB Output isn't correct
66 Incorrect 299 ms 84792 KB Output isn't correct
67 Incorrect 287 ms 84748 KB Output isn't correct
68 Incorrect 249 ms 68348 KB Output isn't correct
69 Incorrect 470 ms 117616 KB Output isn't correct
70 Execution timed out 1033 ms 61968 KB Time limit exceeded
71 Incorrect 443 ms 117740 KB Output isn't correct
72 Incorrect 396 ms 117672 KB Output isn't correct
73 Incorrect 385 ms 117668 KB Output isn't correct
74 Incorrect 414 ms 117768 KB Output isn't correct
75 Incorrect 402 ms 117660 KB Output isn't correct
76 Incorrect 395 ms 117664 KB Output isn't correct
77 Incorrect 397 ms 117744 KB Output isn't correct
78 Incorrect 387 ms 117736 KB Output isn't correct
79 Incorrect 494 ms 117672 KB Output isn't correct
80 Incorrect 491 ms 117740 KB Output isn't correct
81 Incorrect 479 ms 117704 KB Output isn't correct
82 Incorrect 371 ms 84984 KB Output isn't correct
83 Incorrect 383 ms 117692 KB Output isn't correct
84 Incorrect 494 ms 117664 KB Output isn't correct
85 Incorrect 398 ms 117864 KB Output isn't correct
86 Incorrect 204 ms 60236 KB Output isn't correct
87 Incorrect 401 ms 117736 KB Output isn't correct
88 Incorrect 385 ms 117716 KB Output isn't correct
89 Incorrect 333 ms 84988 KB Output isn't correct
90 Execution timed out 1046 ms 61764 KB Time limit exceeded
91 Incorrect 532 ms 84812 KB Output isn't correct
92 Incorrect 423 ms 84720 KB Output isn't correct
93 Incorrect 212 ms 60324 KB Output isn't correct
94 Incorrect 320 ms 84716 KB Output isn't correct
95 Incorrect 372 ms 84892 KB Output isn't correct
96 Incorrect 362 ms 84948 KB Output isn't correct
97 Incorrect 201 ms 60144 KB Output isn't correct
98 Incorrect 371 ms 84760 KB Output isn't correct
99 Incorrect 336 ms 84784 KB Output isn't correct
100 Incorrect 201 ms 60112 KB Output isn't correct