QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#65222 | #2489. Emperor's Palace | Sa3tElSefr | AC ✓ | 170ms | 50280kb | C++23 | 2.7kb | 2022-11-28 06:38:47 | 2022-11-28 06:38:51 |
Judging History
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,我给组数据试试?
詳細信息
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'