QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#63605 | #2489. Emperor's Palace | triplem5ds# | AC ✓ | 410ms | 49880kb | C++20 | 3.2kb | 2022-11-22 20:54:34 | 2022-11-22 20:54:35 |
Judging History
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'