QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#63605#2489. Emperor's Palacetriplem5ds#AC ✓410ms49880kbC++203.2kb2022-11-22 20:54:342022-11-22 20:54:35

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-22 20:54:35]
  • Judged
  • Verdict: AC
  • Time: 410ms
  • Memory: 49880kb
  • [2022-11-22 20:54:34]
  • Submitted

answer

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

#include "bits/stdc++.h"

#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace std;
using namespace __gnu_pbds;

#define pb push_back
#define F first
#define S second
#define f(i, a, b)  for(int i = a; i < b; i++)
#define all(a)  a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define sz(x) (int)(x).size()
#define mp(x,y) make_pair(x,y)
#define popCnt(x) (__builtin_popcountll(x))
//#define int ll

using ll = long long;
using ii = pair<int, int>;
using ull = unsigned long long;

const int N = 2e5+5, LG = 18, MOD = (119 << 23) + 1;
const long double PI = acos(-1);
const long double EPS = 1e-7;

const int dx[] = {1,-1,1,-1};
const int dy[] = {1,-1,-1,1};

int n, m;
vector<string> grid;
vector<vector<int>> cnt;

int ans = -1;
int mxSuffix[1000006];
int mxPrefix[1000006];
int nxt[1000006];
int v[1000006], ptr;
int solve(int n) {
    if(n < 5)
        return -1;
    for(int i = 0; i < n; i++) {
        mxPrefix[i] = v[i];
        if(i)mxPrefix[i] = max(mxPrefix[i], mxPrefix[i-1]);
    }

    for(int i = n - 1; i >= 0; --i) {
        mxSuffix[i] = v[i];
        if(i + 1 != n) {
            mxSuffix[i] = max(mxSuffix[i], mxSuffix[i + 1]);
        }
    }

    int ret = -1;
    for(int i = 2; i + 2 < n; i++) {

        for(int j = max(2,int(ans-n)/3+1); j <= v[i]; j++) {
            int lo = 0, hi = i - 2;
            while(lo < hi) {
                int md = lo + (hi-lo) / 2;
                if(mxPrefix[md] >= j)
                    hi = md;
                else
                    lo = md + 1;
            }
            int L = lo;
            lo = i + 2, hi = n - 1;
            while(lo < hi) {
                int md = lo + (hi - lo + 1) / 2;
                if(mxSuffix[md] >= j)
                    lo = md;
                else
                    hi = md - 1;
            }
            int R = lo;
            if(v[L] >= j && v[R] >= j) {
                ret = max(ret, (R-L+1) + (j-1) * 3);
            }   else break;
        }
    }

    return ret;
}
void doWork() {
    cin >> n >> m;
    grid.resize(n + 1);
    for(int i = 1; i <= n; i++) {
        cin >> grid[i];
        grid[i] = "#" + grid[i];
    }

    for(int col = m; col >= 1; --col) {
        for(int i = 1; i <= n; i++) {
            if(grid[i][col] == '#') nxt[i]  = 0;
            else nxt[i] += 1;
        }
        for(int i = 1, j = 1; i <= n; i = j) {
            if(grid[i][col] == '#')j = i + 1;
            else {
                ptr = 0;
                for(;j <= n && grid[j][col] == '.'; j++)
                    v[ptr++] = nxt[j];
                ans = max(ans, solve(ptr));
            }
        }
    }

    cout << ans << '\n';

}
int32_t main() {
#ifdef ONLINE_JUDGE
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif // ONLINE_JUDGE

    int t = 1;
//    cin >> t;
    while (t--) {
        doWork();
    }
    return 0;
}

///Look at my code ya codeomk


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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3368kb

input:

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

output:

14

result:

ok single line: '14'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3244kb

input:

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

output:

12

result:

ok single line: '12'

Test #3:

score: 0
Accepted
time: 2ms
memory: 3408kb

input:

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

output:

37

result:

ok single line: '37'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3264kb

input:

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

output:

-1

result:

ok single line: '-1'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3484kb

input:

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

output:

17

result:

ok single line: '17'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3268kb

input:

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

output:

-1

result:

ok single line: '-1'

Test #7:

score: 0
Accepted
time: 2ms
memory: 3240kb

input:

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

output:

38

result:

ok single line: '38'

Test #8:

score: 0
Accepted
time: 2ms
memory: 3284kb

input:

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

output:

48

result:

ok single line: '48'

Test #9:

score: 0
Accepted
time: 2ms
memory: 3288kb

input:

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

output:

58

result:

ok single line: '58'

Test #10:

score: 0
Accepted
time: 2ms
memory: 3244kb

input:

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

output:

19

result:

ok single line: '19'

Test #11:

score: 0
Accepted
time: 2ms
memory: 3504kb

input:

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

output:

10

result:

ok single line: '10'

Test #12:

score: 0
Accepted
time: 2ms
memory: 3236kb

input:

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

output:

25

result:

ok single line: '25'

Test #13:

score: 0
Accepted
time: 2ms
memory: 3348kb

input:

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

output:

89

result:

ok single line: '89'

Test #14:

score: 0
Accepted
time: 13ms
memory: 4316kb

input:

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

output:

-1

result:

ok single line: '-1'

Test #15:

score: 0
Accepted
time: 46ms
memory: 7940kb

input:

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

output:

10

result:

ok single line: '10'

Test #16:

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

input:

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

output:

9

result:

ok single line: '9'

Test #17:

score: 0
Accepted
time: 10ms
memory: 4484kb

input:

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

output:

9

result:

ok single line: '9'

Test #18:

score: 0
Accepted
time: 54ms
memory: 7908kb

input:

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

output:

-1

result:

ok single line: '-1'

Test #19:

score: 0
Accepted
time: 58ms
memory: 8284kb

input:

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

output:

9

result:

ok single line: '9'

Test #20:

score: 0
Accepted
time: 17ms
memory: 4304kb

input:

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

output:

16

result:

ok single line: '16'

Test #21:

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

input:

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

output:

16

result:

ok single line: '16'

Test #22:

score: 0
Accepted
time: 77ms
memory: 8196kb

input:

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

output:

16

result:

ok single line: '16'

Test #23:

score: 0
Accepted
time: 10ms
memory: 4444kb

input:

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

output:

21

result:

ok single line: '21'

Test #24:

score: 0
Accepted
time: 67ms
memory: 7884kb

input:

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

output:

18

result:

ok single line: '18'

Test #25:

score: 0
Accepted
time: 70ms
memory: 8200kb

input:

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

output:

21

result:

ok single line: '21'

Test #26:

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

input:

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

output:

122

result:

ok single line: '122'

Test #27:

score: 0
Accepted
time: 61ms
memory: 7832kb

input:

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

output:

119

result:

ok single line: '119'

Test #28:

score: 0
Accepted
time: 62ms
memory: 8036kb

input:

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

output:

117

result:

ok single line: '117'

Test #29:

score: 0
Accepted
time: 14ms
memory: 4564kb

input:

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

output:

231

result:

ok single line: '231'

Test #30:

score: 0
Accepted
time: 54ms
memory: 8016kb

input:

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

output:

263

result:

ok single line: '263'

Test #31:

score: 0
Accepted
time: 53ms
memory: 8280kb

input:

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

output:

249

result:

ok single line: '249'

Test #32:

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

input:

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

output:

712

result:

ok single line: '712'

Test #33:

score: 0
Accepted
time: 39ms
memory: 7960kb

input:

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

output:

718

result:

ok single line: '718'

Test #34:

score: 0
Accepted
time: 57ms
memory: 8236kb

input:

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

output:

774

result:

ok single line: '774'

Test #35:

score: 0
Accepted
time: 14ms
memory: 4376kb

input:

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

output:

2452

result:

ok single line: '2452'

Test #36:

score: 0
Accepted
time: 50ms
memory: 7964kb

input:

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

output:

2860

result:

ok single line: '2860'

Test #37:

score: 0
Accepted
time: 57ms
memory: 8136kb

input:

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

output:

2954

result:

ok single line: '2954'

Test #38:

score: 0
Accepted
time: 25ms
memory: 4360kb

input:

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

output:

3981

result:

ok single line: '3981'

Test #39:

score: 0
Accepted
time: 80ms
memory: 7876kb

input:

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

output:

15703

result:

ok single line: '15703'

Test #40:

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

input:

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

output:

7465

result:

ok single line: '7465'

Test #41:

score: 0
Accepted
time: 41ms
memory: 4496kb

input:

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

output:

3997

result:

ok single line: '3997'

Test #42:

score: 0
Accepted
time: 157ms
memory: 8028kb

input:

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

output:

15991

result:

ok single line: '15991'

Test #43:

score: 0
Accepted
time: 199ms
memory: 8284kb

input:

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

output:

7993

result:

ok single line: '7993'

Test #44:

score: 0
Accepted
time: 36ms
memory: 10640kb

input:

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

output:

3000002

result:

ok single line: '3000002'

Test #45:

score: 0
Accepted
time: 39ms
memory: 10764kb

input:

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

output:

11

result:

ok single line: '11'

Test #46:

score: 0
Accepted
time: 42ms
memory: 10688kb

input:

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

output:

29

result:

ok single line: '29'

Test #47:

score: 0
Accepted
time: 33ms
memory: 10616kb

input:

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

output:

74

result:

ok single line: '74'

Test #48:

score: 0
Accepted
time: 33ms
memory: 10744kb

input:

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

output:

134

result:

ok single line: '134'

Test #49:

score: 0
Accepted
time: 25ms
memory: 10764kb

input:

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

output:

401

result:

ok single line: '401'

Test #50:

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

input:

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

output:

1055

result:

ok single line: '1055'

Test #51:

score: 0
Accepted
time: 33ms
memory: 10716kb

input:

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

output:

9746

result:

ok single line: '9746'

Test #52:

score: 0
Accepted
time: 41ms
memory: 10712kb

input:

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

output:

38702

result:

ok single line: '38702'

Test #53:

score: 0
Accepted
time: 38ms
memory: 10712kb

input:

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

output:

191681

result:

ok single line: '191681'

Test #54:

score: 0
Accepted
time: 410ms
memory: 49880kb

input:

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

output:

1000012

result:

ok single line: '1000012'

Test #55:

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

input:

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

output:

19

result:

ok single line: '19'

Test #56:

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

input:

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

output:

43

result:

ok single line: '43'

Test #57:

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

input:

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

output:

76

result:

ok single line: '76'

Test #58:

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

input:

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

output:

145

result:

ok single line: '145'

Test #59:

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

input:

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

output:

390

result:

ok single line: '390'

Test #60:

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

input:

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

output:

1094

result:

ok single line: '1094'

Test #61:

score: 0
Accepted
time: 116ms
memory: 38272kb

input:

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

output:

10331

result:

ok single line: '10331'

Test #62:

score: 0
Accepted
time: 136ms
memory: 38488kb

input:

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

output:

28657

result:

ok single line: '28657'

Test #63:

score: 0
Accepted
time: 141ms
memory: 40608kb

input:

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

output:

206131

result:

ok single line: '206131'

Test #64:

score: 0
Accepted
time: 365ms
memory: 14044kb

input:

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

output:

100147

result:

ok single line: '100147'

Test #65:

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

input:

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

output:

23

result:

ok single line: '23'

Test #66:

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

input:

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

output:

51

result:

ok single line: '51'

Test #67:

score: 0
Accepted
time: 76ms
memory: 12596kb

input:

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

output:

113

result:

ok single line: '113'

Test #68:

score: 0
Accepted
time: 78ms
memory: 12608kb

input:

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

output:

218

result:

ok single line: '218'

Test #69:

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

input:

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

output:

542

result:

ok single line: '542'

Test #70:

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

input:

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

output:

1324

result:

ok single line: '1324'

Test #71:

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

input:

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

output:

11669

result:

ok single line: '11669'

Test #72:

score: 0
Accepted
time: 381ms
memory: 26456kb

input:

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

output:

500027

result:

ok single line: '500027'

Test #73:

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

input:

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

output:

85147

result:

ok single line: '85147'

Test #74:

score: 0
Accepted
time: 100ms
memory: 22424kb

input:

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

output:

169843

result:

ok single line: '169843'

Test #75:

score: 0
Accepted
time: 93ms
memory: 22096kb

input:

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

output:

135226

result:

ok single line: '135226'

Test #76:

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

input:

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

output:

10

result:

ok single line: '10'

Test #77:

score: 0
Accepted
time: 115ms
memory: 24088kb

input:

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

output:

285700

result:

ok single line: '285700'

Test #78:

score: 0
Accepted
time: 152ms
memory: 24884kb

input:

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

output:

370255

result:

ok single line: '370255'

Test #79:

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

input:

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

output:

278036

result:

ok single line: '278036'

Test #80:

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

input:

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

output:

105245

result:

ok single line: '105245'

Test #81:

score: 0
Accepted
time: 94ms
memory: 23304kb

input:

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

output:

220986

result:

ok single line: '220986'

Test #82:

score: 0
Accepted
time: 212ms
memory: 25248kb

input:

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

output:

413729

result:

ok single line: '413729'

Test #83:

score: 0
Accepted
time: 380ms
memory: 14012kb

input:

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

output:

100147

result:

ok single line: '100147'

Test #84:

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

input:

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

output:

55204

result:

ok single line: '55204'

Test #85:

score: 0
Accepted
time: 66ms
memory: 13272kb

input:

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

output:

33108

result:

ok single line: '33108'

Test #86:

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

input:

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

output:

31180

result:

ok single line: '31180'

Test #87:

score: 0
Accepted
time: 75ms
memory: 13484kb

input:

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

output:

51584

result:

ok single line: '51584'

Test #88:

score: 0
Accepted
time: 80ms
memory: 13124kb

input:

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

output:

47103

result:

ok single line: '47103'

Test #89:

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

input:

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

output:

48196

result:

ok single line: '48196'

Test #90:

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

input:

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

output:

40980

result:

ok single line: '40980'

Test #91:

score: 0
Accepted
time: 76ms
memory: 13536kb

input:

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

output:

67806

result:

ok single line: '67806'

Test #92:

score: 0
Accepted
time: 76ms
memory: 12932kb

input:

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

output:

11004

result:

ok single line: '11004'

Test #93:

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

input:

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

output:

38963

result:

ok single line: '38963'

Test #94:

score: 0
Accepted
time: 282ms
memory: 8560kb

input:

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

output:

11497

result:

ok single line: '11497'

Test #95:

score: 0
Accepted
time: 80ms
memory: 8400kb

input:

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

output:

2619

result:

ok single line: '2619'

Test #96:

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

input:

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

output:

7165

result:

ok single line: '7165'

Test #97:

score: 0
Accepted
time: 66ms
memory: 8536kb

input:

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

output:

8836

result:

ok single line: '8836'

Test #98:

score: 0
Accepted
time: 54ms
memory: 8432kb

input:

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

output:

4282

result:

ok single line: '4282'

Test #99:

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

input:

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

output:

4691

result:

ok single line: '4691'

Test #100:

score: 0
Accepted
time: 62ms
memory: 8380kb

input:

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

output:

4915

result:

ok single line: '4915'

Test #101:

score: 0
Accepted
time: 66ms
memory: 8388kb

input:

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

output:

6643

result:

ok single line: '6643'

Test #102:

score: 0
Accepted
time: 64ms
memory: 8528kb

input:

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

output:

7915

result:

ok single line: '7915'

Test #103:

score: 0
Accepted
time: 66ms
memory: 8412kb

input:

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

output:

9285

result:

ok single line: '9285'

Test #104:

score: 0
Accepted
time: 200ms
memory: 8544kb

input:

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

output:

9677

result:

ok single line: '9677'