QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#693533#5267. Bricks in the WallKenoCarteWA 31ms3668kbC++203.9kb2024-10-31 16:20:312024-10-31 16:20:34

Judging History

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

  • [2024-10-31 16:20:34]
  • 评测
  • 测评结果:WA
  • 用时:31ms
  • 内存:3668kb
  • [2024-10-31 16:20:31]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define rrep(i, a, b) for (int i = a; i >= b; i--)
#define debug(x) cout << #x << ":" << x << endl
#define INF 0x7fffffff
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

vector<vector<char>> mp;
vector<vector<int>> dpl,dpr,dpu,dpd;
vector<vector<int>> ml,mr,mu,md;
int n,m;
signed main(){
    IOS;
    int T;cin>>T;
    while(T--){
        cin>>n>>m;
        mp.clear();
        dpl.clear(),dpr.clear(),dpu.clear(),dpd.clear();
        ml.clear(),mr.clear(),mu.clear(),md.clear();
        mp.resize(n+2),dpl.resize(n+2),dpr.resize(n+2),dpu.resize(n+2),dpd.resize(n+2);
        ml.resize(n+2),mr.resize(n+2),mu.resize(n+2),md.resize(n+2);
        rep(i,0,n+1) mp[i].resize(m+2,0),dpl[i].resize(m+2,0),dpr[i].resize(m+2,0),dpu[i].resize(m+2,0),dpd[i].resize(m+2,0);
        rep(i,0,n+1) ml[i].resize(m+2,0),mr[i].resize(m+2,0),mu[i].resize(m+2,0),md[i].resize(m+2,0);
        rep(i,1,n)
            rep(j,1,m)
                cin>>mp[i][j];
        int l1=0,l2=0,r1=0,r2=0;
        rep(i,1,n){
            int l=0;
            rep(j,1,m){
                dpr[i][j]=((mp[i][j-1]=='#')?1:dpr[i][j-1]+1);
                if(mp[i][j]=='#') dpr[i][j]=0;
                l=max(l,dpr[i][j]);
                ml[i][j]=max(ml[i][j-1],dpr[i][j]); 
            }
            if(l>l1) l2=l1,l1=l;
            else if(l>l2) l2=l;
        }
        rrep(i,n,1){
            rrep(j,m,1){
                dpl[i][j]=((mp[i][j+1]=='#')?1:dpl[i][j+1]+1);
                if(mp[i][j]=='#') dpl[i][j]=0;
                mr[i][j]=max(mr[i][j+1],dpl[i][j]); 
            }
        }
        rep(j,1,m){
            int r=0;
            rep(i,1,n){
                dpd[i][j]=((mp[i-1][j]=='#')?1:dpd[i-1][j]+1);
                if(mp[i][j]=='#') dpd[i][j]=0;
                r=max(r,dpd[i][j]);
                mu[i][j]=max(mu[i-1][j],dpd[i][j]);
            }
            if(r>r1) r2=r1,r1=r;
            else if(r>r2) r2=r;
        }
        rrep(j,m,1){
            rrep(i,n,1){
                dpu[i][j]=((mp[i+1][j]=='#')?1:dpu[i+1][j]+1);
                if(mp[i][j]=='#') dpu[i][j]=0;
                md[i][j]=max(md[i+1][j],dpu[i][j]);
            }
        }
        // rep(i,1,n){
        //     rep(j,1,m){
        //         cout<<dpu[i][j]<<" ";
        //     }
        //     cout<<'\n';
        // }
        int ans=max(l1+l2,r1+r2);
        rep(i,1,n){
            rep(j,1,m){
                //if(mp[i][j]=='#') continue;
                int a,b,t1,t2,t3,t4,t5,t6;
                t1=ml[i][j]+mr[i][j];
                t2=ml[i][j]+mu[i][j];
                t3=ml[i][j]+md[i][j];
                t4=mr[i][j]+mu[i][j];
                t5=mr[i][j]+md[i][j];
                t6=mu[i][j]+md[i][j];
                if(dpr[i][j]==ml[i][j]&&dpl[i][j]==mr[i][j]) t1--;
                if(dpr[i][j]==ml[i][j]&&dpd[i][j]==mu[i][j]) t2--;
                if(dpr[i][j]==ml[i][j]&&dpu[i][j]==md[i][j]) t3--;
                if(dpl[i][j]==mr[i][j]&&dpd[i][j]==mu[i][j]) t4--;
                if(dpl[i][j]==mr[i][j]&&dpu[i][j]==md[i][j]) t5--;
                if(dpd[i][j]==mu[i][j]&&dpu[i][j]==md[i][j]) t6--;
                a=dpr[i][j]+dpl[i][j]-1+max(dpu[i][j],dpd[i][j])-1;
                b=dpu[i][j]+dpd[i][j]-1+max(dpr[i][j],dpl[i][j])-1;
                if(mu[i][j]>dpd[i][j]) a=max(a,dpr[i][j]+dpl[i][j]-1+mu[i][j]);
                if(md[i][j]>dpu[i][j]) a=max(a,dpr[i][j]+dpl[i][j]-1+md[i][j]);
                if(ml[i][j]>dpr[i][j]) b=max(b,dpu[i][j]+dpd[i][j]-1+ml[i][j]);
                if(mr[i][j]>dpl[i][j]) b=max(b,dpu[i][j]+dpd[i][j]-1+mr[i][j]);
                // debug(a);
                // debug(b);
                int t=max(max(max(t1,t2),max(t3,t4)),max(t5,t6));
                ans=max(max(a,b),max(ans,t));
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 3652kb

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 558th numbers differ - expected: '7', found: '6'