oj.uz

Submission #388290

# Submission time Handle Problem Language Result Execution time Memory
388290 2021-04-10T19:13:20 Z patrikpavic2 Bomb (IZhO17_bomb) C++17
78 / 100
 684 ms 90332 KB 
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
 
#define PB push_back
 
using namespace std;
 
const int N = 2505;
 
int n, m;
char s[N][N];
int A[N][N], B[N][N];
 
int par[N], L[N], R[N], un[N], nula[N];
int S[N];
 
int pr(int x){
	if(x == par[x]) return x;
	return par[x] = pr(par[x]);
}
 
void mrg(int x, int y){
	if(x < 0 || y >= m || !un[x] || !un[y]) return;
//	printf("mrg %d %d\n", x, y);
	x = pr(x), y = pr(y);
	if(x == y) return;
	if(nula[x]) S[R[x] - L[x] + 1]--; 
	if(nula[y]) S[R[y] - L[y] + 1]--;
	if(R[x] - L[x] > R[y] - L[y]){
		par[y] = x; R[x] = R[y];
		nula[x] |= nula[y];
		if(nula[x])
			S[R[x] - L[x] + 1]++;
	}
	else{
		par[x] = y; L[y] = L[x];
		nula[y] |= nula[x];
		if(nula[y])
			S[R[y] - L[y] + 1]++;
	}
}
 
vector < int > kon[N];
int ans[N];
 
void odradi_redak(int rd){
	for(int i = 0;i <= m;i++) S[i] = 0;
	for(int i = 0;i <= n;i++) kon[i].clear();
	for(int i = 0;i < m;i++){
		un[i] = 0; 
		if(s[rd][i] == '0') continue;
		par[i] = i; nula[i] = (B[rd][i] == 1);
		L[i] = i, R[i] = i;
		kon[A[rd][i]].PB(i);
		if(nula[i]) S[0]++;
	}
	if(!S[0]) return;
	int cur = 0;
	for(int i = n;i >= 1;i--){
		for(int x : kon[i]){
			if(nula[x])
				S[0]--, S[1]++;
		//	printf("x = %d nula = %d\n", x, nula[x]);
			un[x] = 1;
			mrg(x - 1, x);
			mrg(x, x + 1);
		}
		while(!S[cur]) cur++;
		//printf("rd = %d i = %d cur = %d\n", rd, i, cur);
		ans[i] = min(ans[i], cur);
	}
}
 
int main(){
	//freopen("bomb.in", "r", stdin);
	//freopen("bomb.out", "w", stdout);
	scanf("%d%d", &n, &m);
	int fin = n * m;
	for(int i = 0;i < n;i++)
		for(int j = 0;j < m;j++)
			scanf(" %c", &s[i][j]);
	for(int bla = 0;bla < 2;bla++){
		memset(A, 0, sizeof(A));
		memset(B, 0, sizeof(B));
		for(int i = 0;i < n;i++)
			for(int j = 0;j < m;j++)
				A[i][j] = (1 + (i ? A[i - 1][j] : 0)) * (s[i][j] - '0');
		for(int i = n - 1;i >= 0;i--)
			for(int j = 0;j < m;j++)
				B[i][j] = (1 + B[i + 1][j]) * (s[i][j] - '0');
		int min_j = n, min_i = m;
		for(int i = 0;i < n;i++)
			for(int j = 0;j < m;j++)
				if(s[i][j] == '1') min_j = min(min_j, A[i][j] + B[i][j] - 1);
		for(int i = 0;i < n;i++){
			for(int j = 0;j < m;){
				if(s[i][j] == '0'){
					j++; continue;
				}
				int jj = j;
				while(j < m && s[i][j] == '1') j++;
				min_i = min(min_i, j - jj);
			}
		}
		for(int i = 1;i <= n;i++) ans[i] = 0;
		for(int i = 1;i <= min_j;i++) ans[i] = min_i;
		for(int i = 0;i < n;i++) odradi_redak(i);
		int sol = 1;
		for(int i = 1;i <= n;i++){
			sol = max(sol, ans[i] * i);
			//printf("ans[ %d ] = %d\n", i, ans[i]);
		}
		fin = min(fin, sol);
		for(int i = 0;n - i - 1 > i;i++){
			for(int j = 0;j < m;j++)
				swap(s[i][j], s[n - i - 1][j]);
		}
	}
	printf("%d\n", fin);
	return 0;
}
 
/*
5 6
000000
111110
111110
111110
001000
 
*/

Compilation message

bomb.cpp: In function 'int main()':
bomb.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   79 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
bomb.cpp:83:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   83 |    scanf(" %c", &s[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
78.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 49496 KB Output is correct
2 Correct 27 ms 49460 KB Output is correct
3 Correct 42 ms 55556 KB Output is correct
4 Correct 42 ms 55628 KB Output is correct
5 Correct 27 ms 49472 KB Output is correct
6 Correct 27 ms 49484 KB Output is correct
7 Correct 27 ms 49456 KB Output is correct
8 Correct 27 ms 49540 KB Output is correct
9 Incorrect 26 ms 49472 KB Output isn't correct
10 Correct 27 ms 49468 KB Output is correct
11 Correct 25 ms 49508 KB Output is correct
12 Correct 26 ms 49484 KB Output is correct
13 Correct 32 ms 49512 KB Output is correct
14 Correct 27 ms 49488 KB Output is correct
15 Correct 31 ms 49516 KB Output is correct
16 Correct 32 ms 49464 KB Output is correct
17 Correct 32 ms 49588 KB Output is correct
18 Correct 29 ms 49580 KB Output is correct
19 Incorrect 29 ms 49612 KB Output isn't correct
20 Correct 28 ms 49700 KB Output is correct
21 Correct 32 ms 49584 KB Output is correct
22 Correct 27 ms 49612 KB Output is correct
23 Incorrect 27 ms 49736 KB Output isn't correct
24 Incorrect 27 ms 49648 KB Output isn't correct
25 Correct 28 ms 49640 KB Output is correct
26 Correct 29 ms 49792 KB Output is correct
27 Correct 46 ms 50396 KB Output is correct
28 Correct 40 ms 50120 KB Output is correct
29 Correct 51 ms 50756 KB Output is correct
30 Incorrect 67 ms 50652 KB Output isn't correct
31 Correct 41 ms 50244 KB Output is correct
32 Incorrect 40 ms 50480 KB Output isn't correct
33 Correct 54 ms 50696 KB Output is correct
34 Correct 35 ms 50312 KB Output is correct
35 Incorrect 48 ms 50616 KB Output isn't correct
36 Correct 53 ms 51496 KB Output is correct
37 Correct 33 ms 49488 KB Output is correct
38 Correct 620 ms 90252 KB Output is correct
39 Correct 29 ms 49472 KB Output is correct
40 Correct 110 ms 54088 KB Output is correct
41 Correct 29 ms 49484 KB Output is correct
42 Correct 30 ms 49716 KB Output is correct
43 Correct 638 ms 60568 KB Output is correct
44 Correct 47 ms 50956 KB Output is correct
45 Correct 621 ms 70056 KB Output is correct
46 Correct 595 ms 55764 KB Output is correct
47 Correct 609 ms 70324 KB Output is correct
48 Correct 606 ms 66028 KB Output is correct
49 Correct 684 ms 89412 KB Output is correct
50 Correct 611 ms 66984 KB Output is correct
51 Correct 591 ms 66776 KB Output is correct
52 Correct 591 ms 66244 KB Output is correct
53 Correct 582 ms 65848 KB Output is correct
54 Correct 599 ms 65656 KB Output is correct
55 Correct 557 ms 65716 KB Output is correct
56 Correct 612 ms 89768 KB Output is correct
57 Correct 540 ms 65944 KB Output is correct
58 Correct 554 ms 66308 KB Output is correct
59 Correct 532 ms 65796 KB Output is correct
60 Correct 645 ms 72896 KB Output is correct
61 Correct 615 ms 89356 KB Output is correct
62 Correct 596 ms 86004 KB Output is correct
63 Correct 604 ms 90332 KB Output is correct
64 Correct 532 ms 63640 KB Output is correct
65 Correct 571 ms 65776 KB Output is correct
66 Correct 565 ms 66188 KB Output is correct
67 Correct 606 ms 68208 KB Output is correct
68 Correct 615 ms 70716 KB Output is correct
69 Correct 537 ms 66120 KB Output is correct
70 Incorrect 342 ms 55524 KB Output isn't correct
71 Incorrect 518 ms 58384 KB Output isn't correct
72 Correct 537 ms 58976 KB Output is correct
73 Correct 533 ms 58648 KB Output is correct
74 Incorrect 520 ms 58556 KB Output isn't correct
75 Incorrect 530 ms 60020 KB Output isn't correct
76 Correct 523 ms 58696 KB Output is correct
77 Correct 543 ms 59596 KB Output is correct
78 Correct 537 ms 58820 KB Output is correct
79 Incorrect 500 ms 55572 KB Output isn't correct
80 Incorrect 503 ms 55656 KB Output isn't correct
81 Incorrect 510 ms 56260 KB Output isn't correct
82 Correct 530 ms 59716 KB Output is correct
83 Incorrect 542 ms 59188 KB Output isn't correct
84 Incorrect 500 ms 55640 KB Output isn't correct
85 Incorrect 526 ms 59796 KB Output isn't correct
86 Incorrect 599 ms 87100 KB Output isn't correct
87 Correct 531 ms 61280 KB Output is correct
88 Correct 562 ms 59336 KB Output is correct
89 Correct 563 ms 70136 KB Output is correct
90 Incorrect 357 ms 57112 KB Output isn't correct
91 Correct 544 ms 66172 KB Output is correct
92 Correct 570 ms 67396 KB Output is correct
93 Correct 591 ms 86120 KB Output is correct
94 Correct 555 ms 69060 KB Output is correct
95 Incorrect 533 ms 59208 KB Output isn't correct
96 Correct 548 ms 59040 KB Output is correct
97 Correct 604 ms 86932 KB Output is correct
98 Correct 539 ms 60700 KB Output is correct
99 Incorrect 554 ms 68680 KB Output isn't correct
100 Incorrect 611 ms 85440 KB Output isn't correct