oj.uz

Submission #697254

# Submission time Handle Problem Language Result Execution time Memory
697254 2023-02-09T01:21:25 Z allllekssssa Bomb (IZhO17_bomb) C++14
57 / 100
 1000 ms 78436 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(400, (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 << 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;
}

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
57.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 17 ms 30420 KB Output is correct
4 Correct 20 ms 30452 KB Output is correct
5 Correct 36 ms 344 KB Output is correct
6 Correct 6 ms 348 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 1204 KB Output is correct
19 Correct 6 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 1632 KB Output is correct
24 Correct 5 ms 1360 KB Output is correct
25 Correct 10 ms 1620 KB Output is correct
26 Correct 8 ms 1632 KB Output is correct
27 Correct 132 ms 4692 KB Output is correct
28 Correct 271 ms 5076 KB Output is correct
29 Correct 330 ms 6456 KB Output is correct
30 Correct 687 ms 7696 KB Output is correct
31 Correct 509 ms 6088 KB Output is correct
32 Correct 479 ms 6996 KB Output is correct
33 Correct 794 ms 8084 KB Output is correct
34 Correct 125 ms 5528 KB Output is correct
35 Correct 604 ms 8084 KB Output is correct
36 Correct 701 ms 8088 KB Output is correct
37 Correct 1 ms 468 KB Output is correct
38 Correct 277 ms 76564 KB Output is correct
39 Correct 1 ms 468 KB Output is correct
40 Incorrect 39 ms 19860 KB Output isn't correct
41 Correct 1 ms 468 KB Output is correct
42 Correct 20 ms 1632 KB Output is correct
43 Correct 283 ms 76532 KB Output is correct
44 Execution timed out 1008 ms 8084 KB Time limit exceeded
45 Incorrect 352 ms 76648 KB Output isn't correct
46 Correct 298 ms 76628 KB Output is correct
47 Incorrect 372 ms 76532 KB Output isn't correct
48 Correct 355 ms 76636 KB Output is correct
49 Correct 313 ms 76644 KB Output is correct
50 Incorrect 340 ms 76640 KB Output isn't correct
51 Incorrect 372 ms 77528 KB Output isn't correct
52 Correct 397 ms 77532 KB Output is correct
53 Incorrect 358 ms 78420 KB Output isn't correct
54 Correct 348 ms 78436 KB Output is correct
55 Incorrect 404 ms 78420 KB Output isn't correct
56 Correct 349 ms 78096 KB Output is correct
57 Incorrect 368 ms 78148 KB Output isn't correct
58 Incorrect 395 ms 78172 KB Output isn't correct
59 Correct 345 ms 78104 KB Output is correct
60 Correct 351 ms 78120 KB Output is correct
61 Correct 356 ms 78168 KB Output is correct
62 Correct 400 ms 78120 KB Output is correct
63 Correct 351 ms 78164 KB Output is correct
64 Correct 324 ms 78164 KB Output is correct
65 Correct 401 ms 78172 KB Output is correct
66 Incorrect 309 ms 78164 KB Output isn't correct
67 Correct 366 ms 78140 KB Output is correct
68 Incorrect 352 ms 78136 KB Output isn't correct
69 Correct 333 ms 78092 KB Output is correct
70 Incorrect 213 ms 62640 KB Output isn't correct
71 Incorrect 459 ms 78136 KB Output isn't correct
72 Incorrect 479 ms 78260 KB Output isn't correct
73 Incorrect 341 ms 78264 KB Output isn't correct
74 Incorrect 319 ms 76536 KB Output isn't correct
75 Incorrect 334 ms 76636 KB Output isn't correct
76 Incorrect 276 ms 76620 KB Output isn't correct
77 Incorrect 298 ms 76644 KB Output isn't correct
78 Incorrect 304 ms 76556 KB Output isn't correct
79 Incorrect 407 ms 76636 KB Output isn't correct
80 Incorrect 287 ms 76632 KB Output isn't correct
81 Incorrect 294 ms 76632 KB Output isn't correct
82 Incorrect 284 ms 76664 KB Output isn't correct
83 Incorrect 292 ms 76636 KB Output isn't correct
84 Incorrect 290 ms 76640 KB Output isn't correct
85 Incorrect 287 ms 76632 KB Output isn't correct
86 Incorrect 291 ms 76628 KB Output isn't correct
87 Incorrect 312 ms 76628 KB Output isn't correct
88 Incorrect 304 ms 76548 KB Output isn't correct
89 Incorrect 285 ms 76536 KB Output isn't correct
90 Incorrect 233 ms 62456 KB Output isn't correct
91 Incorrect 302 ms 77944 KB Output isn't correct
92 Incorrect 296 ms 78056 KB Output isn't correct
93 Incorrect 314 ms 77972 KB Output isn't correct
94 Incorrect 303 ms 77936 KB Output isn't correct
95 Incorrect 397 ms 77960 KB Output isn't correct
96 Incorrect 301 ms 78040 KB Output isn't correct
97 Incorrect 313 ms 78044 KB Output isn't correct
98 Incorrect 341 ms 78040 KB Output isn't correct
99 Incorrect 370 ms 77940 KB Output isn't correct
100 Incorrect 300 ms 77932 KB Output isn't correct