QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #619269 | #5267. Bricks in the Wall | TokaiZaopen | WA | 112ms | 3812kb | C++20 | 4.2kb | 2024-10-07 13:42:41 | 2024-10-07 13:42:42 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int solve()
{
int n, m;
cin >> n >> m;
vector<string> a(n);
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
vector<vector<pair<int, int>>> x(n, vector<pair<int, int>>(m));
auto y = x;
multiset<int> x_mx, y_mx;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (a[i][j] == '.')
{
int l = j, r = j;
while (r < m && a[i][r] == '.')
{
x[i][r].first = r - l;
r++;
}
x_mx.insert(r - l);
r--;
while (l <= r)
{
x[i][l].second = r - l;
l++;
}
j = l;
}
}
}
for (int j = 0; j < m; j++)
{
for (int i = 0; i < n; i++)
{
if (a[i][j] == '.')
{
int l = i, r = i;
while (r < n && a[r][j] == '.')
{
y[r][j].first = r - l;
r++;
}
y_mx.insert(r - l);
r--;
while (l <= r)
{
y[l][j].second = r - l;
l++;
}
i = l;
}
}
}
int ans = 0;
if (x_mx.size() > 0)
{
int t = 0;
auto it = x_mx.end();
--it;
if (x_mx.size() > 1)
{
t += *it;
it--;
t += *it;
}
else
{
t += *it;
}
ans = max(ans, t);
}
if (y_mx.size() > 0)
{
int t = 0;
auto it = y_mx.end();
--it;
if (y_mx.size() > 1)
{
t += *it;
it--;
t += *it;
}
else
{
t += *it;
}
ans = max(ans, t);
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (a[i][j] == '.')
{
vector<int> tmp;
vector<int> del;
int l = j, r = j;
while (r < m && a[i][r] == '.')
{
del.emplace_back(y[i][r].first);
del.emplace_back(y[i][r].second);
tmp.emplace_back(y[i][r].first + y[i][r].second + 1);
y_mx.erase(y[i][r].first + y[i][r].second + 1);
y_mx.emplace(y[i][r].first);
y_mx.emplace(y[i][r].second);
r++;
}
ans = max(ans, r - j + *--y_mx.end());
r--;
j = r;
for (auto &it : tmp)
y_mx.emplace(it);
for (auto &it : del)
y_mx.erase(it);
}
}
}
for (int j = 0; j < m; j++)
{
for (int i = 0; i < n; i++)
{
if (a[i][j] == '.')
{
vector<int> tmp;
vector<int> del;
int l = i, r = i;
while (r < n && a[r][j] == '.')
{
del.emplace_back(x[r][j].first);
del.emplace_back(x[r][j].second);
tmp.emplace_back(x[r][j].first + x[r][j].second + 1);
x_mx.erase(x[r][j].first + x[r][j].second + 1);
x_mx.emplace(x[r][j].first);
x_mx.emplace(x[r][j].second);
r++;
}
ans = max(ans, r - i + *--x_mx.end());
r--;
i = r;
for (auto &it : tmp)
x_mx.emplace(it);
for (auto &it : del)
x_mx.erase(it);
}
}
}
cout << ans << "\n";
return 0;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int test = 1;
cin >> test;
while (test--)
{
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3812kb
input:
5 2 2 .. .. 4 5 ###.# #.... .##.# #.#.# 2 1 . . 2 3 ### #.# 5 4 ##.# ..#. #.#. .... #.##
output:
4 6 2 1 7
result:
ok 5 number(s): "4 6 2 1 7"
Test #2:
score: -100
Wrong Answer
time: 112ms
memory: 3632kb
input:
10000 1 6 ..#..# 5 7 #..##.# ..###.# .####.. .##.##. ..#.#.# 1 7 #.####. 10 5 ##..# ###.# ....# #.#.. ##.## ###.# #.... ##.## ...## ..... 1 2 .# 1 3 ##. 7 6 ####.. #####. #...#. ..#..# ..##.# ##.#.. #..##. 5 4 ..## ..#. ..## ..#. ##.# 5 6 .##..# .#.... ##.#.# #..### ##.... 1 6 .#.### 1 2 ## 5 5 ##.....
output:
4 7 2 9 1 1 6 8 8 2 0 6 3 4 4 8 12 4 10 12 8 5 8 3 5 8 1 6 8 4 6 12 7 4 6 2 5 6 3 10 5 5 8 3 4 4 7 8 4 8 6 6 6 4 4 13 3 3 7 7 2 8 3 6 6 4 5 6 11 6 6 6 6 6 9 1 7 7 8 3 7 3 8 10 3 5 4 7 9 5 2 8 6 4 6 2 7 4 2 5 7 10 4 8 8 8 9 8 8 6 2 9 3 9 10 7 4 6 7 8 5 6 7 9 4 8 11 5 6 4 9 2 8 2 3 8 6 7 11 7 6 12 6 1...
result:
wrong answer 1684th numbers differ - expected: '12', found: '11'