oj.uz

Submission #697250

# Submission time Handle Problem Language Result Execution time Memory
697250 2023-02-09T01:14:20 Z allllekssssa Bomb (IZhO17_bomb) C++14
41 / 100
 1000 ms 117072 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 + len - 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
41.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 19 ms 30344 KB Output is correct
4 Correct 20 ms 30436 KB Output is correct
5 Correct 42 ms 344 KB Output is correct
6 Correct 7 ms 340 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 0 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 2 ms 468 KB Output is correct
17 Correct 4 ms 1108 KB Output is correct
18 Correct 4 ms 1108 KB Output is correct
19 Correct 6 ms 1492 KB Output is correct
20 Correct 6 ms 1516 KB Output is correct
21 Correct 4 ms 980 KB Output is correct
22 Correct 6 ms 1236 KB Output is correct
23 Correct 12 ms 1636 KB Output is correct
24 Correct 5 ms 1360 KB Output is correct
25 Correct 10 ms 1632 KB Output is correct
26 Correct 9 ms 1620 KB Output is correct
27 Correct 139 ms 4768 KB Output is correct
28 Correct 280 ms 5080 KB Output is correct
29 Correct 349 ms 6448 KB Output is correct
30 Correct 736 ms 7700 KB Output is correct
31 Correct 525 ms 6076 KB Output is correct
32 Correct 527 ms 6996 KB Output is correct
33 Correct 824 ms 8088 KB Output is correct
34 Correct 125 ms 5460 KB Output is correct
35 Correct 604 ms 8084 KB Output is correct
36 Correct 724 ms 8092 KB Output is correct
37 Correct 1 ms 468 KB Output is correct
38 Incorrect 172 ms 51184 KB Output isn't correct
39 Correct 1 ms 468 KB Output is correct
40 Incorrect 25 ms 13268 KB Output isn't correct
41 Correct 1 ms 468 KB Output is correct
42 Correct 12 ms 1636 KB Output is correct
43 Incorrect 337 ms 67740 KB Output isn't correct
44 Correct 979 ms 8088 KB Output is correct
45 Incorrect 299 ms 84128 KB Output isn't correct
46 Incorrect 329 ms 84096 KB Output isn't correct
47 Incorrect 299 ms 84068 KB Output isn't correct
48 Incorrect 324 ms 84116 KB Output isn't correct
49 Incorrect 168 ms 51296 KB Output isn't correct
50 Incorrect 312 ms 84076 KB Output isn't correct
51 Incorrect 323 ms 84144 KB Output isn't correct
52 Incorrect 321 ms 84176 KB Output isn't correct
53 Incorrect 320 ms 84120 KB Output isn't correct
54 Incorrect 410 ms 116952 KB Output isn't correct
55 Incorrect 446 ms 116940 KB Output isn't correct
56 Incorrect 185 ms 51276 KB Output isn't correct
57 Incorrect 484 ms 116872 KB Output isn't correct
58 Incorrect 425 ms 117016 KB Output isn't correct
59 Incorrect 420 ms 116972 KB Output isn't correct
60 Incorrect 334 ms 84160 KB Output isn't correct
61 Incorrect 163 ms 51172 KB Output isn't correct
62 Incorrect 164 ms 51148 KB Output isn't correct
63 Incorrect 165 ms 51220 KB Output isn't correct
64 Incorrect 417 ms 116996 KB Output isn't correct
65 Incorrect 344 ms 84132 KB Output isn't correct
66 Incorrect 331 ms 84120 KB Output isn't correct
67 Incorrect 312 ms 84112 KB Output isn't correct
68 Incorrect 280 ms 67732 KB Output isn't correct
69 Incorrect 421 ms 116972 KB Output isn't correct
70 Execution timed out 1082 ms 61404 KB Time limit exceeded
71 Incorrect 456 ms 117032 KB Output isn't correct
72 Incorrect 451 ms 116968 KB Output isn't correct
73 Incorrect 421 ms 117000 KB Output isn't correct
74 Incorrect 443 ms 116972 KB Output isn't correct
75 Incorrect 421 ms 116948 KB Output isn't correct
76 Incorrect 425 ms 116940 KB Output isn't correct
77 Incorrect 410 ms 116904 KB Output isn't correct
78 Incorrect 415 ms 116880 KB Output isn't correct
79 Incorrect 515 ms 116928 KB Output isn't correct
80 Incorrect 518 ms 116944 KB Output isn't correct
81 Incorrect 509 ms 116916 KB Output isn't correct
82 Incorrect 398 ms 84128 KB Output isn't correct
83 Incorrect 409 ms 117072 KB Output isn't correct
84 Incorrect 506 ms 116960 KB Output isn't correct
85 Incorrect 429 ms 116968 KB Output isn't correct
86 Incorrect 229 ms 59432 KB Output isn't correct
87 Incorrect 431 ms 116972 KB Output isn't correct
88 Incorrect 403 ms 116900 KB Output isn't correct
89 Incorrect 359 ms 84096 KB Output isn't correct
90 Execution timed out 1095 ms 61260 KB Time limit exceeded
91 Incorrect 388 ms 84148 KB Output isn't correct
92 Incorrect 358 ms 84112 KB Output isn't correct
93 Incorrect 242 ms 59496 KB Output isn't correct
94 Incorrect 349 ms 84200 KB Output isn't correct
95 Incorrect 392 ms 84164 KB Output isn't correct
96 Incorrect 402 ms 84140 KB Output isn't correct
97 Incorrect 234 ms 59516 KB Output isn't correct
98 Incorrect 402 ms 84096 KB Output isn't correct
99 Incorrect 358 ms 84128 KB Output isn't correct
100 Incorrect 254 ms 59528 KB Output isn't correct