QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#65222#2489. Emperor's PalaceSa3tElSefrAC ✓170ms50280kbC++232.7kb2022-11-28 06:38:472022-11-28 06:38:51

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-28 06:38:51]
  • 评测
  • 测评结果:AC
  • 用时:170ms
  • 内存:50280kb
  • [2022-11-28 06:38:47]
  • 提交

answer

#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,fma")

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

#define ll long long
#define ld long double


const int N = 1e6 + 5, mod = 998244353;

int n, m, cnt[N], ans = -1;
string grid[N];

void solve(vector<int> &nums) {
    // cout << "Size = " << nums.size() << '\n';
    // for (auto &i : nums) 
    //     cout << i << ' ';
    // cout << endl;
    vector<int> prefixMax(nums.size()), suffixMax(nums.size());
    for (int i = 0; i < nums.size(); ++i) {
        prefixMax[i] = (i ? max(nums[i], prefixMax[i - 1]) : nums[i]);
    }
    for (int i = int(nums.size()) - 1; i >= 0; --i) {
        suffixMax[i] = (i + 1 != nums.size() ? max(nums[i], suffixMax[i + 1]) : nums[i]);
    }
    for (int i = 2; i + 2 < nums.size(); ++i) {
        for (int len = max(1, (ans - int(nums.size())) / 3 + 1); len <= nums[i]; ++len) {
            int lw = 0, hi = i - 2;
            while (lw < hi) {
                int mid = lw + hi >> 1;
                if (prefixMax[mid] < len) {
                    lw = mid + 1;
                } else {
                    hi = mid;
                }
            }
            int st = hi;
            lw = i + 2, hi = int(nums.size()) - 1;
            while (lw < hi) {
                int mid = (lw + hi + 1) >> 1;
                if (suffixMax[mid] < len) {
                    hi = mid - 1;
                } else {
                    lw = mid;
                }
            }
            int en = lw;
            int cur_ans = (en - st + 1) + 3 * len; 
            // cout << st << ' ' << en << ' ' << cur_ans << '\n';
            // cout << len << ' ' << st << ' ' << nums[st] << ' ' << en << ' ' << nums[en] << '\n';
            if (min(nums[st], nums[en]) < len) {
                break;
            }
            ans = max(ans, cur_ans);
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> grid[i];
    }
    for (int j = m - 1; j >= 0; --j) {
        // cout << "j = " << j << '\n'; 
        for (int i = 0; i < n; ++i) {
            cnt[i] = (grid[i][j] == '#' ? 0 : cnt[i] + 1);
        }
        vector<int> nums;
        for (int i = 0; i < n; ++i) {
            if (grid[i][j] == '#') {
                if (nums.size()) {
                    solve(nums);
                    nums.clear();   
                }
            } else {
                nums.push_back(cnt[i] - 1);
            }
        }
        if (nums.size()) {
            solve(nums);
        }
    }
    cout << ans << '\n';
    return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 11ms
memory: 34800kb

input:

6 6
#.....
....#.
..####
....##
..##..
......

output:

14

result:

ok single line: '14'

Test #2:

score: 0
Accepted
time: 9ms
memory: 35080kb

input:

6 6
#.....
...##.
..####
....##
..##..
......

output:

12

result:

ok single line: '12'

Test #3:

score: 0
Accepted
time: 3ms
memory: 35624kb

input:

10 10
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........

output:

37

result:

ok single line: '37'

Test #4:

score: 0
Accepted
time: 11ms
memory: 36680kb

input:

10 10
##########
##########
##########
##########
##########
##########
##########
##########
##########
##########

output:

-1

result:

ok single line: '-1'

Test #5:

score: 0
Accepted
time: 11ms
memory: 36260kb

input:

5 15
..........#.#..
#........#.....
...#...........
..............#
..##.....#.....

output:

17

result:

ok single line: '17'

Test #6:

score: 0
Accepted
time: 3ms
memory: 34888kb

input:

20 6
#..##.
#..#..
######
#..#.#
##..#.
#.##..
#..#..
#.####
#.##.#
#.#.##
##.##.
###.#.
#.##.#
#.....
...##.
#..###
####.#
##.###
###.##
...###

output:

-1

result:

ok single line: '-1'

Test #7:

score: 0
Accepted
time: 7ms
memory: 35084kb

input:

50 50
#..........#.....#.................#..#......#....
....###....#####....#..#.#..#.#.#............##..#
##.....##.#..#.#......#...#.#...........#.###..#..
.#..#.....#..##.......#.....#.....##.........#....
##...###..###...#..##...##.......#..#..........#.#
....##...#..#..............##...##...#....

output:

38

result:

ok single line: '38'

Test #8:

score: 0
Accepted
time: 4ms
memory: 35736kb

input:

50 50
#....#...#...........#........#.................#.
.....#....###....##.....#......#.#...#.......#....
........#.....#....#.#.............#...#...#......
.............#..###.#..........#.........#.#...##.
#...#.#..#.#.........#.....#....................##
...##....#.#......#...........###..#.##...

output:

48

result:

ok single line: '48'

Test #9:

score: 0
Accepted
time: 8ms
memory: 35420kb

input:

50 50
.#.##.........##..........#...........#....#.....#
.......#...#.............#.....#...#.........#....
..........................##......................
.........#.#.........#.##................#...#.#..
.....#............#.#.....#.....#.##........#.##..
...#.#.....#.........##.#....#............

output:

58

result:

ok single line: '58'

Test #10:

score: 0
Accepted
time: 7ms
memory: 36160kb

input:

50 50
...#.#..#..##....#...#.###....#..#..###...####..##
...####.####...#..#.######..###.#..##.###..###....
##..#...#.##..##....#.#..##...#...###..#.#......#.
..#......#..#...#........###.........#.#..#.....#.
...##.....#####.....##.#....##......#.###...##...#
###.....##.##..#.#.##.##..#........####...

output:

19

result:

ok single line: '19'

Test #11:

score: 0
Accepted
time: 8ms
memory: 35996kb

input:

50 50
#.####.######.#########..##...###..##..##.#.####.#
###...###..#...#.#....##.#####..#.##.#.#.###.#.###
####.#.###.#...##....#..#...######..#####.#.###...
#..........#.######.####.##...#.#.###.#.##.##.#.#.
...###..#..#.#.###.###.####.######....#.###.##.#.#
.#####..##.##.#.#.#.#.###.#.###.#.#.###...

output:

10

result:

ok single line: '10'

Test #12:

score: 0
Accepted
time: 4ms
memory: 35508kb

input:

50 50
.......#.........#.....#....#......#.####....#..#.
##..###.......#.....#.....#........#..#...#...#...
...#.###.........#..##.....#.#.....##..#.........#
....###.#.#.......#....##...#.###...........#..##.
.##...#..#.###.......#..##..#....#..#........#...#
..#.#..#........#.#......#...........#....

output:

25

result:

ok single line: '25'

Test #13:

score: 0
Accepted
time: 9ms
memory: 35788kb

input:

50 50
......#.........#.###...#.....#......#............
.....#......#...#..#.#....##....#.#...##.#......#.
.......#............#.#.#.#....#........#.........
#.#.............#........###....#........#..#.#.#.
.......##..............#..#...............#.#..##.
.#...#.#.........#..##...#.#......##......

output:

89

result:

ok single line: '89'

Test #14:

score: 0
Accepted
time: 20ms
memory: 36184kb

input:

1000 1000
#.##########.########################.##.##.##..######################.#.####.###.#.#########.###################.#.#.############.#####.############.####.#..################...#####.#.##.##########..##.#####################..####..##.##.##.#####.#####.###############################.#####...

output:

-1

result:

ok single line: '-1'

Test #15:

score: 0
Accepted
time: 81ms
memory: 41800kb

input:

1000 5000
###.#.############..#..###.#########.##########.#######.####.#.####.#.##################.############.#.#.#.##########.###.####.####.#.##########..###.#######.########.#.######.#########.#####.#..#.##.#####.#.##.#.############################.######..##.###########.##.#########.########.##...

output:

10

result:

ok single line: '10'

Test #16:

score: 0
Accepted
time: 71ms
memory: 40316kb

input:

5000 1000
#####.##..#.#.###.##.#######.#####.#####.############.########.####.########.############.#.####.#.###########.#######.#######.##########.###.##############..#########.##.########.#....####.####..##...##.##.#######.############.#.####.##.##########..###.####.#.####.###.##.#################...

output:

9

result:

ok single line: '9'

Test #17:

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

input:

1000 1000
#####.#..##.######.#####.###.#######.#####.########.###..#####.########..#####.##########...#.#####.##########.##.#####.###########.#.#...###...##############.#.#.##.##..############..#######.#####..####..#######.#########.##.##.###.#########################.#######.#########...#####.#####...

output:

9

result:

ok single line: '9'

Test #18:

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

input:

1000 5000
#..#.#.#########..##.##.########.######.##.##...#####.#.##.#.#############.#.##...######.#####.###.#####.#..#########.###.########.############.#.#################.######.###.#.####.#.###.#...#####.##.###..#.###.##.####..#..########..#.##.#.########..####.##.####.#.#..#.##.##.###..#.######...

output:

-1

result:

ok single line: '-1'

Test #19:

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

input:

5000 1000
..#.########.##.#####.#########..#.#######...##.#..####.###########.#############......#..##.######..#.######.#.##.#####..#####...####.#####.#...###..###.#..#####.#...####.##.####.######.########.###.######.#########.#.###....######.##.####.#########.#.#.####..########.#.####.########..###...

output:

9

result:

ok single line: '9'

Test #20:

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

input:

1000 1000
.##.#..####..###.####.#.##..##.#...#.#.#########.#..####.####.#.######..###.####.#.#.###.#.##.#..####..###..##...##.#..##....##.##..#####..#.#.#.#####..#.###.#.###.##.#.#.###..#..###.####..###....#..#...######.#..##...#.##...#####.##.##.#######...##.#.#..#####.##..##.###.####..##...##..#.#...

output:

16

result:

ok single line: '16'

Test #21:

score: 0
Accepted
time: 128ms
memory: 40852kb

input:

1000 5000
.#####.#####..###..##########..#.#####.###.#...##.#.###.#..####.#.###...#..###.#.####.#.##...###.##...#..#####....##############.#..#.#.##.#########..####.##.##.#.#.#..###...####..#####.#####.##.###########..#.##.#####.#..###..#.##.##.###.#.##.#.###.#.#########.##.##.#.##.###.#..####.#####...

output:

16

result:

ok single line: '16'

Test #22:

score: 0
Accepted
time: 104ms
memory: 41412kb

input:

5000 1000
#.##..#.########.########.#.#.#...#####..##..#.##.######.#.#.###.#.#####.###..############.##.###.##...###...########..##...######.##########.##.#..##.####.####...###.####.########..#.#####......##.##.########..##.##.##..#.##.######.###...#.#.######.#.######.#.######.#...####.#.#..##.#.#.#...

output:

16

result:

ok single line: '16'

Test #23:

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

input:

1000 1000
#..#....#..####.#..###......##.....##...##....#.#...#....#.##...#...#.##.#.#...#.#.#.#...#.#..#..#....#..#.#..####....#......##.#.###..##...#..#.#.####...##.#.##..####.#...#.#######...#..##...#.##.#..####.########....##.##.#.....##..##.#.##.###.#.###...##..#......###.######.#.###....#.#.##...

output:

21

result:

ok single line: '21'

Test #24:

score: 0
Accepted
time: 130ms
memory: 41060kb

input:

1000 5000
##..####...........###.#######.##..##..#.....##.#.....####..#####.###.#.#..####.##..##..#..###.#.#.#.##.##....#...#####..###.#...##...#..#.####.#.##.#.#.#...##........##.#...#.####..#.##.#.#.#.#.#######...#.###..##....##.##..#..####.....#####...###.##..#..#..#.#.####..#.##.#...###......#.#...

output:

18

result:

ok single line: '18'

Test #25:

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

input:

5000 1000
...#.#.#.######.##..##...#.#..#...##....##.####....#.###..#.....##.###.#..#####.###...####..##.####....##..##....#.##..#####...####.......#..#.###.#....#.#..#.#..#.#.#.#..####..##.##....#.#.....###.#......#..###..###..###.#.#.###.###.#####.#...###.###..#.#.#...####.###.##.###.....#..#....#...

output:

21

result:

ok single line: '21'

Test #26:

score: 0
Accepted
time: 22ms
memory: 37048kb

input:

1000 1000
........#..#.......#.......##...#.............#..#..#..........#....#........#...##...........#..........#.............#..#.........#..............#.#..##..##..#..#...#.....#..#............##.#..#....#...............#...##...#...#........#...#..........................##.#.............#......

output:

122

result:

ok single line: '122'

Test #27:

score: 0
Accepted
time: 111ms
memory: 40644kb

input:

1000 5000
.............#...........#........#....#..#.#.#..#..#...##........####.......#.........#.#.........#.....#.#..........#.................#...#..##....#....#.###..#.#....#...##.#.#........................#...............#.#...........#..#...........#.......#..#..##....#......#............#.....

output:

119

result:

ok single line: '119'

Test #28:

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

input:

5000 1000
...###....#.............................#.....#......###...#..#....#.......#.#.....#.....##.......#.#..#.............#..#..............#..#...#....#...#.....#.........##....#............#..............#..#...#.......#...#..#..#.....#..#.##............#...#...#...##.#...#.....#.....#..#.......

output:

117

result:

ok single line: '117'

Test #29:

score: 0
Accepted
time: 22ms
memory: 37212kb

input:

1000 1000
.#........#..#...................#....#.........#.........................#..#..........#..........#......#.....#.........................#.....#.................##..................................#.....#...............................#....#.....#..........#...#..............................

output:

231

result:

ok single line: '231'

Test #30:

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

input:

1000 5000
#.....#...#........................#..#.#..........#....#......................#.....#........##....#.#.#....#...#.....................................#................................#..................##...#..........................#..#..#....#.......###....................................

output:

263

result:

ok single line: '263'

Test #31:

score: 0
Accepted
time: 71ms
memory: 41724kb

input:

5000 1000
........................#............................................................#.....#.............#.#.#...#.#.................................................#......#.............##.............##......##..........#.....#..#..................#........#..#.............#.................

output:

249

result:

ok single line: '249'

Test #32:

score: 0
Accepted
time: 12ms
memory: 35824kb

input:

1000 1000
.............................##.........#.................#...........................................................................................................................#.......#.....#..................................................................#.............................

output:

712

result:

ok single line: '712'

Test #33:

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

input:

1000 5000
...........................................................#...#.......#.....................#......................##......................#...............................................................................#........................................................................

output:

718

result:

ok single line: '718'

Test #34:

score: 0
Accepted
time: 69ms
memory: 40236kb

input:

5000 1000
....#...........................#.............#...............................................................#.................#..................#.................##.....#.............................................................#.............................#.........#..................

output:

774

result:

ok single line: '774'

Test #35:

score: 0
Accepted
time: 16ms
memory: 35900kb

input:

1000 1000
...................................................#............................................#..........................#.....................#........................................................................................#..........................................................

output:

2452

result:

ok single line: '2452'

Test #36:

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

input:

1000 5000
..........................................................................................................#.........................#....#...................................................................................................................................................##......

output:

2860

result:

ok single line: '2860'

Test #37:

score: 0
Accepted
time: 74ms
memory: 41764kb

input:

5000 1000
..........................................................................#..............#............................................#...................................................................................................................................................#..........

output:

2954

result:

ok single line: '2954'

Test #38:

score: 0
Accepted
time: 18ms
memory: 35856kb

input:

1000 1000
.....................................................................................................................................................................................................................................................................................................

output:

3981

result:

ok single line: '3981'

Test #39:

score: 0
Accepted
time: 82ms
memory: 42204kb

input:

1000 5000
.....................................................................................................................................................................................................................................................................................................

output:

15703

result:

ok single line: '15703'

Test #40:

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

input:

5000 1000
.....................................................................................................................................................................................................................................................................................................

output:

7465

result:

ok single line: '7465'

Test #41:

score: 0
Accepted
time: 16ms
memory: 36912kb

input:

1000 1000
.....................................................................................................................................................................................................................................................................................................

output:

3997

result:

ok single line: '3997'

Test #42:

score: 0
Accepted
time: 56ms
memory: 40980kb

input:

1000 5000
.....................................................................................................................................................................................................................................................................................................

output:

15991

result:

ok single line: '15991'

Test #43:

score: 0
Accepted
time: 68ms
memory: 40436kb

input:

5000 1000
.....................................................................................................................................................................................................................................................................................................

output:

7993

result:

ok single line: '7993'

Test #44:

score: 0
Accepted
time: 150ms
memory: 42028kb

input:

5 1000000
.....................................................................................................................................................................................................................................................................................................

output:

3000002

result:

ok single line: '3000002'

Test #45:

score: 0
Accepted
time: 160ms
memory: 41068kb

input:

5 1000000
..#..#..###.#........###..#.######...#.####.##.#.#...#.....#..##..###.....####..####...#.##..###.#...###...#.###..###.#.##.....##.###.#....#.#..###....##.##.#.#..#.#..########..###...#.###..###.###.#.##.#....#...#.#.#..#.##...#..#.#.#.#......#.###.###..##.#.###..#.####...###...#...#......#...

output:

11

result:

ok single line: '11'

Test #46:

score: 0
Accepted
time: 154ms
memory: 42360kb

input:

5 1000000
###.##.##.....##...#...#...........#..#....#....#......#..#...#..#...#..#...#.#......#............##...##.........#.##....#...#.#.#......##.#...............##.#....##...#.#####....#..#...##...##........###.#.....##.#.......#..###..#....#..........#.#....###..##..##.#...#........#........##...

output:

29

result:

ok single line: '29'

Test #47:

score: 0
Accepted
time: 164ms
memory: 41040kb

input:

5 1000000
............##......#.......#.......................#.##.....#.....#.##......##....#......................#..........#......##..........#...#.#...#........#..#.........#.........#.........#.........................#.......#....#......#...#....#............#...........##.......#...............

output:

74

result:

ok single line: '74'

Test #48:

score: 0
Accepted
time: 169ms
memory: 41280kb

input:

5 1000000
.......................#....#......................................##....#.....#.......#.......#..........................................#.#........##............#....#....#.....................##..#...........#....................................#..........#.......#....................#....

output:

134

result:

ok single line: '134'

Test #49:

score: 0
Accepted
time: 162ms
memory: 41072kb

input:

5 1000000
..........................#...........................................................................#...................................................................#............#..........................................................................................#..................

output:

401

result:

ok single line: '401'

Test #50:

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

input:

5 1000000
...#....................................................................................................................................................................................................................................................#............................................

output:

1055

result:

ok single line: '1055'

Test #51:

score: 0
Accepted
time: 159ms
memory: 42196kb

input:

5 1000000
.....................................................................................................................................................................................................................................................................................................

output:

9746

result:

ok single line: '9746'

Test #52:

score: 0
Accepted
time: 150ms
memory: 41796kb

input:

5 1000000
.....................................................................................................................................................................................................................................................................................................

output:

38702

result:

ok single line: '38702'

Test #53:

score: 0
Accepted
time: 155ms
memory: 42628kb

input:

5 1000000
.....................................................................................................................................................................................................................................................................................................

output:

191681

result:

ok single line: '191681'

Test #54:

score: 0
Accepted
time: 156ms
memory: 50280kb

input:

1000000 5
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....

output:

1000012

result:

ok single line: '1000012'

Test #55:

score: 0
Accepted
time: 170ms
memory: 38528kb

input:

1000000 5
#.##.
#...#
#..#.
#...#
.##.#
...##
..##.
.#..#
.####
#...#
#...#
#####
#.#.#
..##.
#.#..
....#
##.##
#..#.
#####
.###.
##.##
.##..
##...
.#..#
....#
#..#.
.#..#
.#...
#.#..
.####
##.#.
.#...
#.#..
..#.#
#.#..
##.##
..##.
#....
.###.
#.#.#
.#..#
...##
#..##
..###
###..
##..#
..#.#
..#.#
##...

output:

19

result:

ok single line: '19'

Test #56:

score: 0
Accepted
time: 165ms
memory: 38632kb

input:

1000000 5
#.#..
..#..
##..#
.#...
##...
#....
..#..
.#...
....#
..###
...##
.....
###.#
..#..
.....
..##.
.#.#.
#..#.
..#..
...#.
..##.
##...
#.##.
.....
#.#.#
.....
..##.
..##.
.....
...##
....#
##.#.
.....
#..#.
.....
.....
.##..
.....
.#...
..###
.#...
#.#..
.#.#.
..##.
...#.
.....
.....
##..#
##...

output:

43

result:

ok single line: '43'

Test #57:

score: 0
Accepted
time: 146ms
memory: 38476kb

input:

1000000 5
.....
..#..
#...#
....#
.....
#....
.....
.....
..##.
...#.
#....
.#...
..#..
.....
.....
#..#.
..#..
.....
##.##
#....
..#..
.....
#....
...#.
.....
.#..#
.....
....#
.#.#.
#...#
#....
..#..
#....
.....
.#.#.
.....
#.#..
.....
.....
..#..
.....
.#...
.....
.....
#....
.....
#..#.
.#...
.....

output:

76

result:

ok single line: '76'

Test #58:

score: 0
Accepted
time: 135ms
memory: 38608kb

input:

1000000 5
.....
.....
.....
...#.
....#
.....
#....
.....
..#..
.....
...#.
.#...
.....
.#...
#....
.....
.....
.....
.##..
.....
.....
.#...
.....
.....
.....
.#...
..#..
.....
..#..
...#.
...#.
.#...
...#.
.....
.....
.....
#..#.
.....
.....
....#
.....
....#
.....
.#...
.....
.....
#....
.....
.....

output:

145

result:

ok single line: '145'

Test #59:

score: 0
Accepted
time: 117ms
memory: 38724kb

input:

1000000 5
.....
#....
.....
.....
.....
.....
.....
.....
.....
#....
.....
#....
.....
....#
.....
.....
.....
.....
.....
#....
..#..
.....
.....
..#..
.....
.....
.....
.....
.....
.....
.#...
.....
....#
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....

output:

390

result:

ok single line: '390'

Test #60:

score: 0
Accepted
time: 127ms
memory: 38656kb

input:

1000000 5
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.#...
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
....#
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....

output:

1094

result:

ok single line: '1094'

Test #61:

score: 0
Accepted
time: 124ms
memory: 38780kb

input:

1000000 5
.....
.....
...#.
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....

output:

10331

result:

ok single line: '10331'

Test #62:

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

input:

1000000 5
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....

output:

28657

result:

ok single line: '28657'

Test #63:

score: 0
Accepted
time: 133ms
memory: 40900kb

input:

1000000 5
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....

output:

206131

result:

ok single line: '206131'

Test #64:

score: 0
Accepted
time: 110ms
memory: 42264kb

input:

100000 50
..................................................
..................................................
..................................................
..................................................
..................................................
......................................

output:

100147

result:

ok single line: '100147'

Test #65:

score: 0
Accepted
time: 138ms
memory: 42228kb

input:

100000 50
#....#..#..#.##...###..#######..###..#.#..#..#.#..
#.#.#####.####..#.#...####...#####.##.....##.#.#.#
.###......##..#.####.....#..#..#..###.#...#..#..#.
###.#.#.##.#.#.#.####.#...#..##.#..##.#.##....##..
...#..#..####...####....#.#.##....#.####...#.##...
...##..#.#####.#....####...#.####.#...

output:

23

result:

ok single line: '23'

Test #66:

score: 0
Accepted
time: 138ms
memory: 42308kb

input:

100000 50
.........##........#......##....####.#..###....#..
...#.#.###....##.##.#......#.#.#.....#.....#.#.#..
##...#....#.#..........##..#.#.....#......##.#.###
..#....#..#.#.#.......##..#..#....##...####...##.#
#####.#..#.##.###.#...#..#..#.###.###.#...#.......
....#..#....#..#.#.#..........#.###...

output:

51

result:

ok single line: '51'

Test #67:

score: 0
Accepted
time: 118ms
memory: 41204kb

input:

100000 50
..#..#..##.#.....#......#.#............#..#.#.....
..##...#........#..................##....#.#....#.
...............#....#.#..................#.....##.
..................#.......#..#....................
.#.#...............#........#.........#...#..#..#.
.#.#...............#..............#...

output:

113

result:

ok single line: '113'

Test #68:

score: 0
Accepted
time: 90ms
memory: 41668kb

input:

100000 50
.#...........................#.......#.......#...#
..........#.......................................
#.................#.............#.................
.........#........................#.##.....#......
.......#.#.#.#....#....................#....#..##.
#........................#......#.....

output:

218

result:

ok single line: '218'

Test #69:

score: 0
Accepted
time: 109ms
memory: 41468kb

input:

100000 50
.#.......................#.............#..........
..............#...................................
.........#........................................
..................................................
..................................................
......................................

output:

542

result:

ok single line: '542'

Test #70:

score: 0
Accepted
time: 88ms
memory: 41272kb

input:

100000 50
..................................................
.........................#...............#........
..................................................
............#...........#...................#.....
..................................#...............
.....................#................

output:

1324

result:

ok single line: '1324'

Test #71:

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

input:

100000 50
..................................................
..................................................
..................................................
..................................................
....................#.............................
......................................

output:

11669

result:

ok single line: '11669'

Test #72:

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

input:

500000 10
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
.......

output:

500027

result:

ok single line: '500027'

Test #73:

score: 0
Accepted
time: 153ms
memory: 37380kb

input:

500000 10
####.#..##
...##...#.
#......#.#
.###.#....
##.##..###
#.###.##.#
#...#.##.#
#...####.#
#..#.#.#..
##..######
.#....#..#
..##.###.#
#....##.#.
.##.#.#..#
#.###..##.
#.#..##.##
##.#.#.#.#
.#..####.#
...#..#.#.
..#.####.#
.#..###..#
##.#.#..##
##.###.#..
.##.##..#.
#..#..#..#
##.###....
.......

output:

85147

result:

ok single line: '85147'

Test #74:

score: 0
Accepted
time: 155ms
memory: 38244kb

input:

500000 10
.##.###.##
##..######
.##..#####
####..####
####.##.#.
##.#####..
##.###..##
##.######.
....###.##
#####.#.##
#..####.##
####.##.##
##########
###...###.
##.###.#.#
######..##
.##..##.#.
..#..###.#
####.#.##.
.##.##.#.#
.#########
#####.#.##
##.##.....
##.##.###.
###..#####
####.#...#
####...

output:

169843

result:

ok single line: '169843'

Test #75:

score: 0
Accepted
time: 134ms
memory: 38032kb

input:

500000 10
###.##..##
##########
.#..######
#.########
..########
###.#..#..
##.####..#
#.########
.##.######
##..#.###.
.##.#..###
#.#.###.#.
##########
.#.####.##
###.#.####
..########
##.###..##
#.##.#.###
.#.#...###
.#...#####
...##.####
.########.
#.###.####
#.#..#...#
.####.##.#
.##.######
####...

output:

135226

result:

ok single line: '135226'

Test #76:

score: 0
Accepted
time: 119ms
memory: 39928kb

input:

500000 10
###.###.#.
######.###
#########.
###..#.###
.#########
##.#######
#######..#
##########
.##..#####
####..#.##
###.####..
##########
##########
.#####.#..
#.#####.#.
#...####.#
.#########
###.######
.####.#.##
#####...##
##..######
#######.##
#########.
#.#.######
#.########
######.###
#.##...

output:

10

result:

ok single line: '10'

Test #77:

score: 0
Accepted
time: 145ms
memory: 39688kb

input:

500000 10
..#.....#.
#...##.#..
..#..#..#.
.#....#..#
##..#.....
.####.....
.##...#...
#......#..
...#...###
.##.......
#.#.#.....
...###....
..#...#..#
.#.#.#....
.##.#.#.##
#.##...#..
##.#.#....
.#........
...###.#..
...#......
#.#.#..#..
.##....###
...#.###..
..#..##...
####...#..
.#..##..#.
####...

output:

285700

result:

ok single line: '285700'

Test #78:

score: 0
Accepted
time: 133ms
memory: 40620kb

input:

500000 10
..........
.......##.
.#..#..#..
......#...
..........
..........
......##..
....#.....
..#......#
..#.#.#...
#..#......
..........
#.#......#
..##......
....#.....
...#....#.
#.........
##.##.##..
......#...
.........#
#....##...
..........
#.........
........#.
##........
........##
.......

output:

370255

result:

ok single line: '370255'

Test #79:

score: 0
Accepted
time: 124ms
memory: 39676kb

input:

500000 10
..........
.##.......
.......#..
..........
..........
#....#....
..........
..#..#....
.....#.##.
....#.....
..........
#...#....#
..#....#..
.....#....
..#..#...#
.#........
........#.
....##....
#.........
....#.....
....#.....
....#.....
..........
........#.
#.........
..........
.......

output:

278036

result:

ok single line: '278036'

Test #80:

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

input:

500000 10
..........
..........
..........
.....#..#.
..........
......#...
..........
..........
..........
..........
..........
..........
..........
........#.
..#.......
..........
..........
..........
..#......#
..........
..........
.#.......#
..........
..........
..........
..........
.......

output:

105245

result:

ok single line: '105245'

Test #81:

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

input:

500000 10
........#.
..........
..........
..........
..........
..........
..........
..........
..........
#.........
..........
..#.......
..........
..........
..........
..........
#.........
....#.....
..........
..........
..........
..........
#.........
..........
..........
..........
.......

output:

220986

result:

ok single line: '220986'

Test #82:

score: 0
Accepted
time: 89ms
memory: 41396kb

input:

500000 10
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
.#........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........
....#.....
..........
.......

output:

413729

result:

ok single line: '413729'

Test #83:

score: 0
Accepted
time: 103ms
memory: 42160kb

input:

100000 50
..................................................
..................................................
..................................................
..................................................
..................................................
......................................

output:

100147

result:

ok single line: '100147'

Test #84:

score: 0
Accepted
time: 163ms
memory: 41532kb

input:

100000 50
#....#..#..#.##...###..#######..###..#.#..#..#.#..
#.#.#####.####..#.#...####...#####.##.....##.#.#.#
.###......##..#.####.....#..#..#..###.#...#..#..#.
###.#.#.##.#.#.#.####.#...#..##.#..##.#.##....##..
...#..#..####...####....#.#.##....#.####...#.##...
...##..#.#####.#....####...#.####.#...

output:

55204

result:

ok single line: '55204'

Test #85:

score: 0
Accepted
time: 133ms
memory: 41392kb

input:

100000 50
.####.#..##..#.#####.#..##.##.###.###..###.######.
####.##.#...####.#.##.#..###...###.##.#.##.#######
####..#.####.##..###########.####.#..#....####.###
#######...#.#####.####......##..#.#.#.####.#.##..#
.###.##.#####.####.########.##.####.#########.####
.###############.###.###.##########...

output:

33108

result:

ok single line: '33108'

Test #86:

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

input:

100000 50
.######..##.######.#.########.####..###..###.###.#
.####..###########..####.#..####.###############.#
#####.####.#.#####..##########.##################.
.####.######.####.##.#..###.###.##################
##..#############.####.####.#.########.#####.#...#
##############.####.#####.###.#####...

output:

31180

result:

ok single line: '31180'

Test #87:

score: 0
Accepted
time: 85ms
memory: 41704kb

input:

100000 50
###..##.#######.##.#.###########.#############.###
##.###.###.####.##.##.###.##.####.########.####.#.
#####.#####.#######################..#.###########
..##.#####..#####.###########.####....############
#######.#################.########.##...##.#######
###.#########..##########.##.######...

output:

51584

result:

ok single line: '51584'

Test #88:

score: 0
Accepted
time: 130ms
memory: 41680kb

input:

100000 50
.........##........#......##....####.#..###....#..
...#.#.###....##.##.#......#.#.#.....#.....#.#.#..
##...#....#.#..........##..#.#.....#......##.#.###
..#....#..#.#.#.......##..#..#....##...####...##.#
#####.#..#.##.###.#...#..#..#.###.###.#...#.......
....#..#....#..#.#.#..........#.###...

output:

47103

result:

ok single line: '47103'

Test #89:

score: 0
Accepted
time: 119ms
memory: 41572kb

input:

100000 50
..#..#..##.#.....#......#.#............#..#.#.....
..##...#........#..................##....#.#....#.
...............#....#.#..................#.....##.
..................#.......#..#....................
.#.#...............#........#.........#...#..#..#.
.#.#...............#..............#...

output:

48196

result:

ok single line: '48196'

Test #90:

score: 0
Accepted
time: 106ms
memory: 41576kb

input:

100000 50
.#...........................#.......#.......#...#
..........#.......................................
#.................#.............#.................
.........#........................#.##.....#......
.......#.#.#.#....#....................#....#..##.
#........................#......#.....

output:

40980

result:

ok single line: '40980'

Test #91:

score: 0
Accepted
time: 89ms
memory: 42008kb

input:

100000 50
.#.......................#.............#..........
..............#...................................
.........#........................................
..................................................
..................................................
......................................

output:

67806

result:

ok single line: '67806'

Test #92:

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

input:

100000 50
..................................................
.........................#...............#........
..................................................
............#...........#...................#.....
..................................#...............
.....................#................

output:

11004

result:

ok single line: '11004'

Test #93:

score: 0
Accepted
time: 95ms
memory: 41672kb

input:

100000 50
..................................................
..................................................
..................................................
..................................................
....................#.............................
......................................

output:

38963

result:

ok single line: '38963'

Test #94:

score: 0
Accepted
time: 101ms
memory: 39856kb

input:

10000 500
.....................................................................................................................................................................................................................................................................................................

output:

11497

result:

ok single line: '11497'

Test #95:

score: 0
Accepted
time: 147ms
memory: 39844kb

input:

10000 500
##.#.##.##.#...##.#.#.#..#..###..##.#..#..#.#.##....#####....##..#.#.##.#....###.#.###......#.###.#...#.....#.#.....####.#.#..#...####..##.#.##.##..####..#...#.#####.#.########..#..#.....##.##..#####..#...#..##.#..##.#....##..#.#..###...##.....##..##.....#.##......#...#.#.#.#..##.##.#..###...

output:

2619

result:

ok single line: '2619'

Test #96:

score: 0
Accepted
time: 127ms
memory: 39808kb

input:

10000 500
.#..#.##..######.#.######.#.###..#######..#..#....#######.####...#..################.###..######.##.#...#...#.#.#..#.##.####.###.######.##.#.###.#.#...###.##..##.#..#.#######..#.#.####.####..##..#....####.#####..##.########.######.#.#####.##.#....######.##.####...#.###..#.#.#..#.#.###.#......

output:

7165

result:

ok single line: '7165'

Test #97:

score: 0
Accepted
time: 95ms
memory: 39752kb

input:

10000 500
#...###..##.#.#######.####.#.#####..#.##.#####.#.####.####.#.#####.######.#########..#.#.###.#..#########..#..#####.#.#.######.#.####.######.#####..##.###...##.#.##.#.##.#..#.##.##.#.##########..###.##..##.########.###########..##..##.#.#.###############.###.#.###.##.##.#.#.#.##.##.....###...

output:

8836

result:

ok single line: '8836'

Test #98:

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

input:

10000 500
.###.#..##.#####.#########.#####.########.##########.####..#######.#.##.#########.##.##.######.#.######...####################.######.###.#.#.#########.#.#.#.############.########..#######.#############.#..############.#####.#####.########.#..############.#########.####.#.###########.##.#....

output:

4282

result:

ok single line: '4282'

Test #99:

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

input:

10000 500
.#..#.#......#.####..#..##.......#......###.#.#...##.#...#..##.........#....#....###.....##..#...#..#.#.##...#....#..##.#......#.#.#...##..#..#..........#.....#..#...#...#....#..........#....#..##.#.####..#.#..#.##...####.##......#..#...#...#.##..##...#..#.###..#....#.......#.##.#..##........

output:

4691

result:

ok single line: '4691'

Test #100:

score: 0
Accepted
time: 106ms
memory: 39940kb

input:

10000 500
.......#...#........##........#........#....................#...#...............#.#........#....#.#..........#..#.....##....#...#......#.....#...........#.........##......#.##....#...#..........#.....#...#.....#........#..#..#....#.#......#..#......#........#......#....#..#.......#...#...#...

output:

4915

result:

ok single line: '4915'

Test #101:

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

input:

10000 500
.....#...........#.............................#............#............................#........##..........#..............#...#...........#..........#............................#.......#...........###..#.....#.........................................##.....#...................#.##........

output:

6643

result:

ok single line: '6643'

Test #102:

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

input:

10000 500
................#..........#..........................................................#.........#.................#............#....#................................................................#..#......#...................#............#...........#........................................

output:

7915

result:

ok single line: '7915'

Test #103:

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

input:

10000 500
......................................................#.......................#......................................................................................#......................#........................................................................................................

output:

9285

result:

ok single line: '9285'

Test #104:

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

input:

10000 500
.....................................................................................................................................................................................................................................................................................................

output:

9677

result:

ok single line: '9677'