QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#817118#5267. Bricks in the WallSGColinAC ✓1038ms264648kbC++173.4kb2024-12-16 20:32:022024-12-16 20:32:04

Judging History

你现在查看的是最新测评结果

  • [2024-12-16 20:32:04]
  • 评测
  • 测评结果:AC
  • 用时:1038ms
  • 内存:264648kb
  • [2024-12-16 20:32:02]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define N 2000007

bool mp[N];

int u[N], d[N], l[N], r[N];

multiset<int, greater<int> > R[N], C[N];

inline void work() {
	int n, m; scanf("%d%d", &n, &m);
	auto p = [&](int x, int y) {return (x - 1) * m + y;};

	for (int i = 1; i <= n; ++i) R[i].clear();
	for (int j = 1; j <= m; ++j) C[j].clear();
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j) {
			char c = getchar();
			while (c != '.' && c != '#') c = getchar();
			int pos = p(i, j);
			mp[pos] = (c == '#');
			u[pos] = d[pos] = l[pos] = r[pos] = 0;
		}
	for (int i = 1; i <= n; ++i)
		for (int j = 1, pos; j <= m; ++j) 
			if (!mp[pos = p(i, j)]) {
				u[pos] = (i > 1 ? u[p(i - 1, j)] + 1 : 1);
				l[pos] = (j > 1 ? l[p(i, j - 1)] + 1 : 1);
			}
	for (int i = n; i; --i)
		for (int j = m, pos; j; --j) 
			if (!mp[pos = p(i, j)]) {
				d[pos] = (i < n ? d[p(i + 1, j)] + 1 : 1);
				r[pos] = (j < m ? r[p(i, j + 1)] + 1 : 1);
			}
	for (int i = 1, pos; i <= n; ++i) {
		if (!mp[pos = p(i, 1)]) R[i].insert(r[pos]);
		for (int j = 1; j < m; ++j)
			if (mp[p(i, j)] && !mp[pos = p(i, j + 1)]) R[i].insert(r[pos]);
	}
	for (int j = 1, pos; j <= m; ++j) {
		if (!mp[pos = p(1, j)]) C[j].insert(d[pos]);
		for (int i = 1; i < n; ++i)
			if (mp[p(i, j)] && !mp[pos = p(i + 1, j)]) C[j].insert(d[pos]);
	}
	int mx = 0, mxx = 0;
	auto upd = [&](int x) {
		if (mx < x) {mxx = mx; mx = x;}
		else if (mxx < x) mxx = x;
	};
	for (int i = 1; i <= n; ++i) {
		int sz = R[i].size();
		if (sz) upd(*R[i].begin());
		if (sz > 1) upd(*++R[i].begin());
	}
	int ans = mx + mxx;
	mx = mxx = 0;
	for (int j = 1; j <= m; ++j) {
		int sz = C[j].size();
		if (sz) upd(*C[j].begin());
		if (sz > 1) upd(*++C[j].begin());
	}
	ans = max(ans, mx + mxx);
	for (int i = 1; i <= n; ++i)
		for (int j = 1, pos; j <= m; ++j) 
			if (!mp[pos = p(i, j)]) 
                ans = max(ans, u[pos] + d[pos] + l[pos] + r[pos] - 2 - min({u[pos], d[pos], l[pos], r[pos]}));
	for (int i = 1; i <= n; ++i)
		for (int j = 1, pos; j <= m; ++j) {
			if (!mp[pos = p(i, j)]) {
				int lr = l[pos] + r[pos] - 1;
				int ud = u[pos] + d[pos] - 1;
				// cut lr
				R[i].erase(R[i].lower_bound(lr));
				R[i].insert(l[pos] - 1); R[i].insert(r[pos] - 1);
				mx = 0; mxx = 0;
				int sz = R[i].size();
				if (sz) upd(*R[i].begin());
				if (sz > 1) upd(*++R[i].begin());
				sz = C[j].size();
				if (sz) upd(*C[j].begin());
				if (sz > 1) upd(*++C[j].begin());
				ans = max(ans, mx + mxx);
				R[i].erase(R[i].lower_bound(l[pos] - 1));
				R[i].erase(R[i].lower_bound(r[pos] - 1));
				R[i].insert(lr);
				// cut ud
				C[j].erase(C[j].lower_bound(ud));
				C[j].insert(u[pos] - 1); C[j].insert(d[pos] - 1);
				mx = 0; mxx = 0;
				sz = R[i].size();
				if (sz) upd(*R[i].begin());
				if (sz > 1) upd(*++R[i].begin());
				sz = C[j].size();
				if (sz) upd(*C[j].begin());
				if (sz > 1) upd(*++C[j].begin());
				ans = max(ans, mx + mxx);
				C[j].erase(C[j].lower_bound(u[pos] - 1));
				C[j].erase(C[j].lower_bound(d[pos] - 1));
				C[j].insert(ud);
			} else {
				mx = 0; mxx = 0;
				int sz = R[i].size();
				if (sz) upd(*R[i].begin());
				if (sz > 1) upd(*++R[i].begin());
				sz = C[j].size();
				if (sz) upd(*C[j].begin());
				if (sz > 1) upd(*++C[j].begin());
				ans = max(ans, mx + mxx);
			}
		}
	printf("%d\n", ans);
}

int main() {
	int t; scanf("%d", &t);
	for (int i = 1; i <= t; ++i) work();
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 23ms
memory: 201148kb

input:

5
2 2
..
..
4 5
###.#
#....
.##.#
#.#.#
2 1
.
.
2 3
###
#.#
5 4
##.#
..#.
#.#.
....
#.##

output:

4
6
2
1
7

result:

ok 5 number(s): "4 6 2 1 7"

Test #2:

score: 0
Accepted
time: 91ms
memory: 199876kb

input:

10000
1 6
..#..#
5 7
#..##.#
..###.#
.####..
.##.##.
..#.#.#
1 7
#.####.
10 5
##..#
###.#
....#
#.#..
##.##
###.#
#....
##.##
...##
.....
1 2
.#
1 3
##.
7 6
####..
#####.
#...#.
..#..#
..##.#
##.#..
#..##.
5 4
..##
..#.
..##
..#.
##.#
5 6
.##..#
.#....
##.#.#
#..###
##....
1 6
.#.###
1 2
##
5 5
##.....

output:

4
7
2
9
1
1
6
8
8
2
0
6
3
4
4
8
12
4
10
12
8
5
8
3
5
8
1
6
8
4
6
12
7
4
6
2
5
6
3
10
5
5
8
3
4
4
7
8
4
8
6
6
6
4
4
13
3
3
7
7
2
8
3
6
6
4
5
6
11
6
6
6
6
6
9
1
7
7
8
3
7
3
8
10
3
5
4
7
9
5
2
8
6
4
6
2
7
4
2
5
7
10
4
8
8
8
9
8
8
6
2
9
3
9
10
7
4
6
7
8
5
6
7
9
4
8
11
5
6
4
9
2
8
2
3
8
6
7
11
7
6
12
6
1...

result:

ok 10000 numbers

Test #3:

score: 0
Accepted
time: 60ms
memory: 200820kb

input:

10000
1 5
#####
9 5
##..#
##.##
.####
#.###
###.#
..#.#
#####
####.
#####
10 9
.########
#.#######
##.#..###
########.
#######.#
########.
#########
#########
#########
###.#####
5 2
##
##
##
##
.#
3 9
#########
#########
#######.#
8 8
########
.#####.#
########
.#######
#######.
###.#..#
#.######
....

output:

0
4
3
1
1
3
0
0
1
3
2
1
2
3
1
3
3
2
2
2
3
2
3
2
5
0
0
1
1
4
0
2
0
1
3
4
0
2
4
3
2
2
1
2
2
2
2
3
3
2
2
2
1
1
2
2
1
2
4
3
1
1
3
2
5
0
3
3
0
4
4
1
3
0
1
2
1
0
2
1
1
1
2
4
2
0
3
0
2
2
2
2
2
2
1
1
2
2
2
1
3
3
2
2
0
0
2
2
1
1
4
1
2
3
0
2
1
2
0
2
4
3
1
2
0
2
1
3
3
3
1
3
4
3
4
2
0
3
3
5
2
0
0
0
2
6
2
2
2
0
...

result:

ok 10000 numbers

Test #4:

score: 0
Accepted
time: 32ms
memory: 200740kb

input:

10000
9 6
######
######
.#####
######
######
######
######
#####.
######
9 7
#######
#######
#######
#######
#######
#######
#######
#######
#######
2 5
#####
#####
7 5
####.
#####
.####
#####
#####
#####
#####
1 4
####
9 6
######
######
######
######
######
######
######
######
######
10 8
########...

output:

2
0
0
2
0
0
2
2
1
2
0
0
1
1
2
0
0
2
0
0
1
2
2
0
0
1
1
2
2
2
2
0
2
2
1
0
0
1
0
2
1
1
1
2
1
3
3
2
0
1
3
0
2
2
1
2
2
1
0
0
2
1
2
2
2
3
1
0
2
1
0
1
1
2
1
1
0
1
3
0
0
0
1
0
1
0
2
2
1
2
0
0
3
0
0
0
0
2
0
2
1
0
0
2
2
1
0
0
2
0
1
0
2
2
1
1
1
0
2
2
2
0
0
0
0
2
1
2
0
2
2
0
0
0
0
2
2
0
0
0
0
2
0
1
2
1
1
2
0
3
...

result:

ok 10000 numbers

Test #5:

score: 0
Accepted
time: 92ms
memory: 199748kb

input:

10000
5 4
....
....
....
....
....
5 2
..
.#
..
..
..
1 8
...#....
8 10
.#..#...#.
.#........
...#......
..........
#.........
.##.......
..........
..........
2 10
..........
........#.
7 6
......
......
......
......
......
...#..
......
2 2
.#
..
9 1
.
.
.
.
.
.
.
.
.
5 1
.
.
.
.
.
9 5
.....
.......

output:

10
8
7
20
18
14
3
9
5
16
20
13
17
18
14
4
5
8
13
9
15
8
9
4
18
18
16
20
16
14
13
8
12
9
9
12
15
18
18
16
10
3
6
13
12
20
12
14
4
1
6
2
20
11
12
12
18
10
18
20
14
10
18
12
8
3
15
8
20
18
17
8
16
6
6
14
12
20
1
5
10
9
16
18
12
11
12
14
8
20
5
20
6
3
16
20
18
10
12
16
16
16
4
20
13
13
12
14
20
19
20
20...

result:

ok 10000 numbers

Test #6:

score: 0
Accepted
time: 84ms
memory: 200636kb

input:

1000
6 16
.##..#.##.######
#.##.###...#..##
##.#####.##.#.##
.##..#.#.#..#...
..#..#.#.#.#....
#.#.#..#.#.#.#.#
8 17
##..#...######.#.
..####.######..#.
###.###.#..#.#.##
..#.#.##..#.#.##.
##.#.#.##.#....##
#..###..#.#.#....
.#.....#...#....#
.#..#.##.##...##.
16 25
.##.###.####.##...#.#####
#..##.#...

output:

9
10
21
9
12
6
13
13
12
7
8
11
9
7
10
8
11
23
10
13
14
14
9
15
17
10
12
13
10
13
12
12
7
10
12
3
14
11
12
13
14
5
14
14
11
14
18
6
12
8
11
15
15
15
10
15
2
12
11
14
9
16
9
17
6
13
6
20
12
2
8
19
16
17
19
13
19
4
18
13
8
11
8
3
13
15
16
15
11
4
11
8
4
11
6
13
16
10
13
16
16
7
13
25
14
20
16
14
3
11
1...

result:

ok 1000 numbers

Test #7:

score: 0
Accepted
time: 96ms
memory: 200148kb

input:

1000
3 185
#...#..##.###.##..#######..##..#.##.##..####.##.......###.##..##.....###.##..#####....######.####.##.###.###.#....###...#.....##.#....#....#..##..#.####.#.##.#.####..#...#####.#.#.##.#.
.#.##.####.#.##..#.#.######....#..##..##..#.#.########.#.##.#.####.#...###......#.#..#.###...#...#.###....

output:

14
5
15
18
12
13
14
10
12
2
14
13
13
12
16
8
13
7
8
14
26
16
11
13
14
11
11
16
14
10
16
14
15
3
16
9
8
16
17
12
11
18
17
4
15
15
10
11
13
2
10
20
6
11
11
7
14
11
13
16
13
14
6
9
15
16
9
15
14
15
11
14
12
16
12
14
8
9
8
16
13
8
11
18
10
13
13
6
13
8
11
10
15
10
15
11
19
6
16
14
9
16
10
16
9
4
15
16
2...

result:

ok 1000 numbers

Test #8:

score: 0
Accepted
time: 113ms
memory: 200280kb

input:

1000
40 2
..
##
.#
..
..
..
..
..
##
.#
..
..
..
..
..
##
#.
#.
.#
..
##
##
..
.#
##
##
##
#.
..
.#
.#
#.
.#
..
##
.#
..
.#
##
#.
19 1
#
.
#
#
#
#
.
#
#
.
#
#
.
#
.
.
#
.
#
24 4
.#..
.##.
#.##
#.##
##..
.###
##.#
##..
#...
#..#
###.
..#.
####
.#.#
.###
#.##
##.#
##.#
.#..
###.
.#.#
....
....
.###
12...

output:

12
3
8
15
16
4
17
12
19
16
16
7
5
18
8
13
7
15
10
18
13
6
16
19
3
8
10
9
14
12
11
12
10
15
17
15
13
11
9
14
1
16
11
14
14
9
17
14
6
10
17
12
17
20
18
15
19
10
17
14
15
6
15
9
13
4
16
12
10
7
10
9
14
12
21
8
15
11
10
9
9
14
15
19
7
5
17
13
10
17
10
10
14
5
18
15
8
11
10
9
17
8
11
9
11
10
12
17
10
10
...

result:

ok 1000 numbers

Test #9:

score: 0
Accepted
time: 86ms
memory: 201556kb

input:

100
2 45
#.###..###.#..#..#...#####.##..#.....##.##.#.
..#..#.#.###.######.#.###...####.#...#.###.##
4 63
.#...####...####.####..#.#...#.###.###...##...#..#.#...##...#..
#.##..##.#.####.#....#.#...########.#.######..##.##.#..###.##..
#..##.#...##.#.#..###..#..#.###.#...........##.#.####..##.#####
.#...

output:

8
16
15
21
22
12
26
19
24
15
21
20
14
19
16
17
1
19
22
18
20
29
18
21
22
16
16
22
27
27
19
24
13
13
18
14
12
15
19
20
18
21
24
20
14
15
17
20
20
22
17
16
26
20
26
20
18
16
23
24
13
18
17
22
18
13
23
23
23
17
17
22
25
16
21
13
13
18
17
16
24
26
17
23
19
6
8
25
20
14
21
21
21
22
15
17
16
15
15
18

result:

ok 100 numbers

Test #10:

score: 0
Accepted
time: 43ms
memory: 200020kb

input:

100
2 72
##.###########.###.############.#########.##########.###########.#######
#...###########.#.##.############.#.######################.##.###.####..
75 58
####.##########.###.#################.#####.##############
#######..###############.######.############.#############
#####################...

output:

5
7
7
6
6
6
6
8
8
6
6
6
6
4
9
6
6
4
7
6
7
7
8
7
6
6
7
4
4
5
4
6
6
7
6
6
6
9
7
4
4
6
4
7
4
6
8
8
6
6
7
7
6
6
6
5
6
6
6
2
7
4
5
8
8
6
7
4
6
2
7
6
7
6
5
6
4
7
3
4
8
6
8
3
6
5
6
4
7
2
6
6
2
4
8
5
4
6
6
3

result:

ok 100 numbers

Test #11:

score: 0
Accepted
time: 27ms
memory: 199900kb

input:

100
43 93
#######################################################################################.#####
#############################################################################################
#############################################################################################
########...

output:

4
3
4
0
3
2
2
3
2
2
2
3
2
4
2
3
2
2
3
4
3
2
2
3
2
3
2
2
2
3
2
2
3
2
2
3
2
2
3
3
2
2
0
0
2
2
2
2
3
0
3
2
3
1
3
2
3
2
2
3
3
4
2
2
3
2
2
2
2
2
2
2
2
2
2
4
2
2
2
3
2
2
2
3
2
2
1
2
2
2
2
2
2
2
0
3
2
2
4
1

result:

ok 100 numbers

Test #12:

score: 0
Accepted
time: 44ms
memory: 198580kb

input:

10
41 499
##########################################.#####################################.#.####.################################.#####.############.#####.######################.#######.###########.######.######################.#.##############################.####.#.#######.###.###########...###.....

output:

9
6
8
9
8
4
8
6
6
6

result:

ok 10 numbers

Test #13:

score: 0
Accepted
time: 79ms
memory: 201872kb

input:

10
41 877
#.##########....##..##.#..###...#...#.###.#.#..#.#.#..##..#..#.##.#.#.##.......#..####..##.#.####.###.##.#...#..#..###...##.#.###.#.#.....###..#.###.#..#....#...#..#.#.##.#.##..#.#.#..##.#...#.#...#.##...###.###.....#.###.#..##.####..###.#.####.###......#....#.##.###.#.###.#..##....####......

output:

28
26
16
27
28
36
21
30
16
23

result:

ok 10 numbers

Test #14:

score: 0
Accepted
time: 51ms
memory: 202316kb

input:

10
859 68
###.##############.##########..#########.##..#...####.##.#.#########
.#.##.#################################################.#######.####
.####.###############..##########.###########.######################
####.#####################.#.##.##.#########.##############.########
########.#####...

output:

8
8
10
6
7
10
7
6
10
9

result:

ok 10 numbers

Test #15:

score: 0
Accepted
time: 97ms
memory: 205524kb

input:

10
963 50
###.##...#....#..#..#...#.##..#.###...#.#..###...#
...####...#..#.##.#..#....###.#.#.##....#.#.##.#..
#....#.#......#######.##.###.###..###.#.#....##..#
.####....#####..#.#.#.#.###.##.#....#...#..###.##.
##..##...#...#.#..#....#.#.#.#.#.##..#.#.#..#..##.
.####.###.....#......####..##.........

output:

27
16
22
20
24
22
18
27
28
31

result:

ok 10 numbers

Test #16:

score: 0
Accepted
time: 35ms
memory: 204092kb

input:

10
23 107
#.####.####.###########..#############.####.#############################.#######.#######.########.########
####.###################.#######.##################.#####.###################.#.###########################
#######.##.#############################...##############.###########.###....

output:

84
173
187
212
57
46
172
39
8
18

result:

ok 10 numbers

Test #17:

score: 0
Accepted
time: 114ms
memory: 202032kb

input:

10
55 78
...#.##.#####....##.##.#...#.#...###.###..#..#.##..##...####.....#.##.#....#.#
.###.#..#.#.#####.#..######....#...#...#..###..#.######..####.##.#..##...#...#
.####...#.##.....#.#.#..#...###.#........##....####.##.##.#..###..##.####....#
#......##.#.......#..##.#.###..#.#......###.#..#..#.##...

output:

91
215
209
239
115
44
140
166
301
446

result:

ok 10 numbers

Test #18:

score: 0
Accepted
time: 83ms
memory: 200712kb

input:

10
3 2515
#..##..#..#..#..#...##...###...###.##..#..###.##..##.##.#.######..##.##..##.###.#....................................................................................................................................................................................................................

output:

4942
402
12899
15672
5915
2113
15630
15104
778
306

result:

ok 10 numbers

Test #19:

score: 0
Accepted
time: 105ms
memory: 203688kb

input:

10
9644 5
##...
####.
#..##
##..#
#...#
.#.#.
..#..
.#..#
#.#.#
..##.
#...#
.#.#.
#..#.
#..#.
##...
.###.
#.##.
##.#.
.#...
###..
####.
.....
.##..
#.##.
.##..
.....
.###.
..#..
...#.
#.#..
...#.
##.#.
...#.
...#.
##...
.###.
.....
.#.#.
.#...
..##.
##.#.
#..#.
###..
#....
#....
#.#..
..#..
##...
.....

output:

18955
9043
17912
8479
12922
14983
15186
15888
15222
6580

result:

ok 10 numbers

Test #20:

score: 0
Accepted
time: 158ms
memory: 200668kb

input:

10
9485 6
......
..#..#
......
##....
......
..##..
.....#
...#..
....#.
...#..
......
....#.
......
......
......
.#....
......
.#.#.#
.#..#.
....#.
#..#..
....#.
#.....
.##...
......
.#....
......
#....#
......
..#...
......
......
......
.#....
..#...
.#....
#.....
.#.#..
......
##.#..
.#....
......

output:

159
172
137
139
160
140
170
152
85
136

result:

ok 10 numbers

Test #21:

score: 0
Accepted
time: 84ms
memory: 200200kb

input:

10
3233 5
.....
.....
.....
.....
.....
.....
.....
..#..
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
..#..
.....
.....
.....
.....
.....
.....
.....
.....
.....
.#...
.....
.....
.....
.....
.....

output:

909
1104
883
1415
414
508
1035
877
986
1050

result:

ok 10 numbers

Test #22:

score: 0
Accepted
time: 920ms
memory: 225900kb

input:

1
1000 1000
........#.#....#...............#....#.#.............#.#........#......#.......#...#....#...........#.............#...#............#..................##......#..#.................................##.....###......#..........#..............#.#.................#.......#...........#..............

output:

213

result:

ok 1 number(s): "213"

Test #23:

score: 0
Accepted
time: 1032ms
memory: 230104kb

input:

1
100000 10
..........
.......#..
.......#..
.........#
#.....#...
........#.
##...#....
.#........
......#...
..#..#...#
........#.
...#......
..........
.#.......#
.#........
..........
..........
.........#
..........
..........
....#.....
.......#..
.#........
..........
.....#..##
......#..#
.....

output:

195

result:

ok 1 number(s): "195"

Test #24:

score: 0
Accepted
time: 73ms
memory: 201256kb

input:

1
10 10000
#.......#.........#........#...............#......#......#..#...........................................#.#.#..#......#............#............#.....#........#.#...#....#...........#..#...............#...#.....#.#.#...#..#............#.#....#...#.................#....#..#......#............

output:

238

result:

ok 1 number(s): "238"

Test #25:

score: 0
Accepted
time: 1016ms
memory: 261920kb

input:

1
1000000 1
#
.
.
.
.
.
.
.
.
.
.
#
.
.
.
.
.
.
.
#
.
.
#
.
.
.
.
.
.
.
.
.
.
.
#
.
#
.
.
.
.
.
.
.
.
.
.
.
.
.
.
#
.
.
.
.
.
.
.
.
.
.
.
.
#
.
.
#
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
#
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
#
.
.
.
.
.
#
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...

output:

211

result:

ok 1 number(s): "211"

Test #26:

score: 0
Accepted
time: 1018ms
memory: 263744kb

input:

1
1 1000000
..#.........#.........................#............................#..................#......#........##................#..#..###...#.#.#......#...#........###.....................#...................................................#..............#....................###.##.................

output:

214

result:

ok 1 number(s): "214"

Test #27:

score: 0
Accepted
time: 48ms
memory: 215280kb

input:

1
1000000 1
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
...

output:

0

result:

ok 1 number(s): "0"

Test #28:

score: 0
Accepted
time: 43ms
memory: 215436kb

input:

1
1 1000000
################################################################################################################################################################################################################################################################################################...

output:

0

result:

ok 1 number(s): "0"

Test #29:

score: 0
Accepted
time: 880ms
memory: 239468kb

input:

1
1000 1000
....####...#..######...#...#..##..###..##..#####..#...##.#####.#...####.#.#..#..##.....#..#.#..#.#....##....##.#..#.###...#..#.########..#..#.#.###.##....#...#.#..#.#...####..#..##..####.....##.#.##.##...##..#.###....#....#....#.#.#...#....####......##....###..####.##......#..###..#........

output:

1223

result:

ok 1 number(s): "1223"

Test #30:

score: 0
Accepted
time: 897ms
memory: 238836kb

input:

1
1000 1000
..##...#..##.#....#.##.#....#...#...#....#######.####.##.###...#.###.#.####..#.#.##.#########.#.#####.#...#..###.#.#.#.#.##...#....#.######...#####.#....##..##.#....###..#.#....#.#.#.#.#.#.##.##...#.##...#..####..#..##....#.##.#.#.#.#.##.###..#####.##..#.####.#.##.#.####.##...##.##.##.#....

output:

1116

result:

ok 1 number(s): "1116"

Test #31:

score: 0
Accepted
time: 885ms
memory: 239312kb

input:

1
1000 1000
..###..#..#.#...#####.#..#.#.###..###.#.##.....##..#####.#..#...##########..###.#.#...######..####..###.#..####.#..##.####...####.#.#..#.#...##.#.##.#.#...####..#..#....#..#..####....#..##.#.#.#...#######...##..####.#######.#..###..#..###.#..#####....##.######...#..#...###.#..#...##.##.....

output:

1153

result:

ok 1 number(s): "1153"

Test #32:

score: 0
Accepted
time: 926ms
memory: 239304kb

input:

1
1000 1000
.#..####..#.####......#.##.####...#.####....#..###....#.#.##.#..#..#..##..#.##..#.#....##.##.###.###.#.#..##.#...#.#..#.#....#.#.##..#.#.##...###.##....#....##..########.##.###..#..#.#..#.......#..##..#.#.##.....#.##..#.#.##.#.###.###.##.#..####..##...#.#..#####.####....###...#.#...#.##....

output:

959

result:

ok 1 number(s): "959"

Test #33:

score: 0
Accepted
time: 191ms
memory: 217892kb

input:

1
1000 1000
...................................................................................................................................................................................................................................................................................................

output:

2000

result:

ok 1 number(s): "2000"

Test #34:

score: 0
Accepted
time: 191ms
memory: 222480kb

input:

1
100000 10
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
.....

output:

200000

result:

ok 1 number(s): "200000"

Test #35:

score: 0
Accepted
time: 40ms
memory: 203292kb

input:

1
10 10000
....................................................................................................................................................................................................................................................................................................

output:

20000

result:

ok 1 number(s): "20000"

Test #36:

score: 0
Accepted
time: 245ms
memory: 264648kb

input:

1
1000000 1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...

output:

1000000

result:

ok 1 number(s): "1000000"

Test #37:

score: 0
Accepted
time: 235ms
memory: 262188kb

input:

1
1 1000000
...................................................................................................................................................................................................................................................................................................

output:

1000000

result:

ok 1 number(s): "1000000"

Test #38:

score: 0
Accepted
time: 266ms
memory: 263136kb

input:

1
1000000 1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...

output:

83540

result:

ok 1 number(s): "83540"

Test #39:

score: 0
Accepted
time: 241ms
memory: 264396kb

input:

1
1 1000000
...................................................................................................................................................................................................................................................................................................

output:

88303

result:

ok 1 number(s): "88303"

Test #40:

score: 0
Accepted
time: 235ms
memory: 215520kb

input:

1
1000 1000
...........................................................................................#.......................................................................................................................................................................................................

output:

2000

result:

ok 1 number(s): "2000"

Test #41:

score: 0
Accepted
time: 261ms
memory: 222208kb

input:

1
100000 10
..........
..........
..........
..........
..........
..........
..........
..........
.........#
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
.....

output:

15559

result:

ok 1 number(s): "15559"

Test #42:

score: 0
Accepted
time: 37ms
memory: 202352kb

input:

1
10 10000
.............................................................................................................................................................................................................#......................................................................................

output:

7395

result:

ok 1 number(s): "7395"

Test #43:

score: 0
Accepted
time: 213ms
memory: 241224kb

input:

1
500000 2
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
....

output:

1000000

result:

ok 1 number(s): "1000000"

Test #44:

score: 0
Accepted
time: 197ms
memory: 239720kb

input:

1
2 500000
....................................................................................................................................................................................................................................................................................................

output:

1000000

result:

ok 1 number(s): "1000000"

Test #45:

score: 0
Accepted
time: 239ms
memory: 238916kb

input:

1
500000 2
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
....

output:

360154

result:

ok 1 number(s): "360154"

Test #46:

score: 0
Accepted
time: 239ms
memory: 239580kb

input:

1
2 500000
....................................................................................................................................................................................................................................................................................................

output:

387653

result:

ok 1 number(s): "387653"

Test #47:

score: 0
Accepted
time: 249ms
memory: 239652kb

input:

1
500000 2
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
....

output:

90498

result:

ok 1 number(s): "90498"

Test #48:

score: 0
Accepted
time: 238ms
memory: 239884kb

input:

1
2 500000
....................................................................................................................................................................................................................................................................................................

output:

81255

result:

ok 1 number(s): "81255"

Test #49:

score: 0
Accepted
time: 322ms
memory: 238952kb

input:

1
500000 2
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
....

output:

15623

result:

ok 1 number(s): "15623"

Test #50:

score: 0
Accepted
time: 290ms
memory: 240844kb

input:

1
2 500000
...................................................................................................................................................................................................................................................................................#................

output:

15179

result:

ok 1 number(s): "15179"

Test #51:

score: 0
Accepted
time: 667ms
memory: 239768kb

input:

1
500000 2
..
..
..
..
..
..
..
..
..
..
..
#.
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
.#
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
.#
..
..
..
....

output:

1769

result:

ok 1 number(s): "1769"

Test #52:

score: 0
Accepted
time: 596ms
memory: 241716kb

input:

1
2 500000
.........................................................................................................#..........................................................................................................................#........................#......................................

output:

2031

result:

ok 1 number(s): "2031"

Test #53:

score: 0
Accepted
time: 1038ms
memory: 243012kb

input:

1
500000 2
..
..
..
..
..
..
..
..
..
##
..
..
.#
..
..
..
..
..
..
..
..
..
#.
.#
..
..
..
.#
#.
..
..
..
..
#.
..
..
..
..
..
..
..
..
..
..
..
..
.#
#.
#.
..
..
..
..
..
#.
..
..
..
..
..
..
#.
..
..
..
..
..
..
.#
.#
..
..
.#
..
.#
#.
..
..
..
..
..
..
..
..
..
..
..
..
.#
..
..
..
..
.#
..
..
....

output:

243

result:

ok 1 number(s): "243"

Test #54:

score: 0
Accepted
time: 953ms
memory: 242712kb

input:

1
2 500000
...##.........#..........................#.................#..#................................#..#...............##.............#.#........#...........#...........#..........#......#..............................#.............#.........#.##..............#..........#...#..............#......

output:

221

result:

ok 1 number(s): "221"

Test #55:

score: 0
Accepted
time: 120ms
memory: 223948kb

input:

1
500000 2
##
##
##
##
##
##
#.
##
##
##
##
##
##
##
##
##
#.
##
##
##
##
##
##
##
#.
##
##
##
##
.#
##
#.
##
##
##
##
##
##
##
##
##
##
##
##
##
##
##
.#
##
##
##
##
##
#.
##
##
.#
##
##
##
##
##
##
##
##
##
.#
##
##
##
##
#.
##
##
##
##
##
#.
#.
##
##
##
##
##
##
##
##
##
##
##
##
#.
##
##
##
##
#...

output:

12

result:

ok 1 number(s): "12"

Test #56:

score: 0
Accepted
time: 132ms
memory: 224144kb

input:

1
2 500000
###############.###########.###########.##############.#######.#########################.##################################.#########.###.#.#.###########.#######.#.########.##.#############..#####.########.########.#####.#####.##.#.###############.########.###.####.############.##########...

output:

10

result:

ok 1 number(s): "10"