oj.uz

Submission #697256

# Submission time Handle Problem Language Result Execution time Memory
697256 2023-02-09T01:22:48 Z allllekssssa Bomb (IZhO17_bomb) C++14
52 / 100
 897 ms 51396 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(800, (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 1 ms 212 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 10 ms 20308 KB Output is correct
4 Correct 10 ms 20308 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 212 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 1 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 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 4 ms 1108 KB Output is correct
19 Correct 6 ms 1492 KB Output is correct
20 Correct 6 ms 1492 KB Output is correct
21 Correct 3 ms 980 KB Output is correct
22 Correct 5 ms 1236 KB Output is correct
23 Correct 8 ms 1640 KB Output is correct
24 Correct 6 ms 1364 KB Output is correct
25 Correct 10 ms 1628 KB Output is correct
26 Correct 9 ms 1632 KB Output is correct
27 Correct 125 ms 4776 KB Output is correct
28 Correct 271 ms 5076 KB Output is correct
29 Correct 330 ms 6456 KB Output is correct
30 Correct 616 ms 7704 KB Output is correct
31 Correct 465 ms 6088 KB Output is correct
32 Correct 465 ms 6996 KB Output is correct
33 Correct 744 ms 8020 KB Output is correct
34 Correct 119 ms 5520 KB Output is correct
35 Correct 547 ms 8084 KB Output is correct
36 Correct 656 ms 8084 KB Output is correct
37 Correct 1 ms 468 KB Output is correct
38 Correct 165 ms 51076 KB Output is correct
39 Correct 1 ms 468 KB Output is correct
40 Incorrect 24 ms 13344 KB Output isn't correct
41 Correct 1 ms 468 KB Output is correct
42 Correct 11 ms 1620 KB Output is correct
43 Incorrect 335 ms 51084 KB Output isn't correct
44 Correct 897 ms 8104 KB Output is correct
45 Incorrect 314 ms 51200 KB Output isn't correct
46 Correct 320 ms 51276 KB Output is correct
47 Incorrect 321 ms 51208 KB Output isn't correct
48 Correct 201 ms 51080 KB Output is correct
49 Incorrect 161 ms 51176 KB Output isn't correct
50 Incorrect 207 ms 51080 KB Output isn't correct
51 Incorrect 203 ms 51156 KB Output isn't correct
52 Correct 201 ms 51144 KB Output is correct
53 Incorrect 183 ms 51080 KB Output isn't correct
54 Correct 225 ms 51312 KB Output is correct
55 Incorrect 206 ms 51148 KB Output isn't correct
56 Correct 180 ms 51188 KB Output is correct
57 Incorrect 180 ms 51112 KB Output isn't correct
58 Correct 211 ms 51200 KB Output is correct
59 Correct 207 ms 51148 KB Output is correct
60 Incorrect 163 ms 51084 KB Output isn't correct
61 Incorrect 165 ms 51176 KB Output isn't correct
62 Incorrect 162 ms 51108 KB Output isn't correct
63 Incorrect 163 ms 51148 KB Output isn't correct
64 Incorrect 166 ms 51088 KB Output isn't correct
65 Correct 197 ms 51212 KB Output is correct
66 Incorrect 166 ms 51168 KB Output isn't correct
67 Correct 212 ms 51148 KB Output is correct
68 Incorrect 217 ms 51224 KB Output isn't correct
69 Correct 178 ms 51192 KB Output is correct
70 Incorrect 109 ms 41012 KB Output isn't correct
71 Incorrect 165 ms 51148 KB Output isn't correct
72 Incorrect 170 ms 51216 KB Output isn't correct
73 Incorrect 163 ms 51148 KB Output isn't correct
74 Incorrect 164 ms 51180 KB Output isn't correct
75 Incorrect 169 ms 51236 KB Output isn't correct
76 Incorrect 164 ms 51148 KB Output isn't correct
77 Incorrect 163 ms 51188 KB Output isn't correct
78 Incorrect 165 ms 51284 KB Output isn't correct
79 Incorrect 167 ms 51116 KB Output isn't correct
80 Incorrect 163 ms 51116 KB Output isn't correct
81 Incorrect 163 ms 51148 KB Output isn't correct
82 Incorrect 166 ms 51252 KB Output isn't correct
83 Incorrect 161 ms 51076 KB Output isn't correct
84 Incorrect 162 ms 51076 KB Output isn't correct
85 Incorrect 168 ms 51148 KB Output isn't correct
86 Incorrect 167 ms 51272 KB Output isn't correct
87 Incorrect 165 ms 51160 KB Output isn't correct
88 Incorrect 164 ms 51180 KB Output isn't correct
89 Incorrect 165 ms 51132 KB Output isn't correct
90 Incorrect 111 ms 40904 KB Output isn't correct
91 Incorrect 163 ms 51164 KB Output isn't correct
92 Incorrect 162 ms 51068 KB Output isn't correct
93 Incorrect 165 ms 51188 KB Output isn't correct
94 Incorrect 166 ms 51116 KB Output isn't correct
95 Incorrect 167 ms 51160 KB Output isn't correct
96 Incorrect 163 ms 51116 KB Output isn't correct
97 Incorrect 167 ms 51148 KB Output isn't correct
98 Incorrect 163 ms 51396 KB Output isn't correct
99 Incorrect 163 ms 51104 KB Output isn't correct
100 Incorrect 162 ms 51084 KB Output isn't correct