QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#673759#5267. Bricks in the WallIllusionaryDominance#WA 31ms3560kbC++202.1kb2024-10-25 09:49:452024-10-25 09:49:46

Judging History

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

  • [2024-10-25 09:49:46]
  • 评测
  • 测评结果:WA
  • 用时:31ms
  • 内存:3560kb
  • [2024-10-25 09:49:45]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using namespace std;
using ll=long long;
#define all(x) (x).begin(), (x).end()

int cal_row(string s)
{
    int r=0, tmp=0;
    for(int j=1;j<s.size();++j) 
    {
        if(s[j]=='#') r=max(r, tmp), tmp=0;
        else ++tmp, r=max(r, tmp);
    }
    return r;
}

int cal1(vector<string> a, int n, int m)
{
    vector<int> num(n);
    for(int i=1;i<=n;++i) num[i-1]=cal_row(a[i]);
    sort(all(num));
    int sum=0;
    for(int i=n-1; i>=0 && i>=n-2; --i) sum+=num[i];
    return sum;
}

int cal2(vector<string> a, int n, int m)
{
    vector pre(n+2, vector<int>(m+2)), suf=pre;
    for(int j=1;j<=m;++j)
    {
        int tmp=0;
        for(int i=1;i<=n;++i)
        {
            pre[i][j]=pre[i-1][j];
            if(a[i][j]=='.') ++tmp, pre[i][j]=max(pre[i][j], tmp);
            else tmp=0;
        }
    }
    
    for(int j=1;j<=m;++j)
    {
        int tmp=0;
        for(int i=n;i;--i)
        {
            if(i<n) suf[i][j]=suf[i+1][j];
            if(a[i][j]=='.') ++tmp, suf[i][j]=max(suf[i][j], tmp);
            else tmp=0;
        }
    }
    
    for(int j=1;j<=m;++j) for(int i=1;i<=n;++i) pre[i][j]=max(pre[i][j], pre[i][j-1]);
    for(int j=m-1; j; --j) for(int i=1;i<=n;++i) suf[i][j]=max(suf[i][j], suf[i][j+1]);
    
    int sum=0;
    
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j) if(a[i][j]=='.')
        {
            int r=j;
            while(r+1<=m && a[i][r+1]=='.') ++r;
            
            sum=max(sum, r-j+1+max({pre[i-1][m], pre[n][j-1], suf[i+1][1], suf[1][r+1]}));
            
            j=r;
        }
        
    }
    
    return sum;
}

void solve()
{
    int n, m;
    cin>>n>>m;
    vector<string> s(n+1);
    for(int i=1;i<=n;++i) cin>>s[i], s[i]=" "+s[i];
    
    vector<string> t(m+1, string(n+1, ' '));
    for(int j=1;j<=m;++j) for(int i=1;i<=n;++i) t[j][i]=s[i][j];
    
    cout << max({cal1(s, n, m), cal1(t, m, n), cal2(s, n, m), cal2(t, m, n)}) << "\n";
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
    
    int T;
    cin>>T;
    while(T--) solve();
}

詳細信息

Test #1:

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

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: 31ms
memory: 3560kb

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:

3
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
4
6
9
1
7
7
8
3
7
3
8
10
3
5
4
7
9
5
2
8
4
4
6
2
7
4
2
5
6
10
4
8
8
8
9
8
8
6
2
9
3
9
10
7
4
6
7
8
5
5
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 1st numbers differ - expected: '4', found: '3'