QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#601599#5267. Bricks in the Wallhuaxiamengjin#WA 28ms125412kbC++142.3kb2024-09-30 08:50:012024-09-30 08:50:02

Judging History

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

  • [2024-09-30 08:50:02]
  • 评测
  • 测评结果:WA
  • 用时:28ms
  • 内存:125412kb
  • [2024-09-30 08:50:01]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<char>a[1001001];
vector<int>g[1001001],f[1001001],ff[1001001],gg[1001001];
int sf[1001001],sg[1001001],pf[1001001],pg[1001001];
void solve(){
	cin>>n>>m;
	for (int i=0;i<=n+1;i++)
	a[i].resize(m+3),f[i].resize(m+3),ff[i].resize(m+3);
	for (int i=0;i<=n+1;i++)
	g[i].resize(m+3),gg[i].resize(m+3);
	for (int i=0;i<=n+1;i++)
	for (int j=0;j<=m+1;j++)
	f[i][j]=ff[i][j]=g[i][j]=gg[i][j]=0;
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++)
	cin>>a[i][j];
	int mx=0,ans=0;

	for (int i=1;i<=n;i++){
		int pre=0;
		for (int j=1;j<=m;j++)
		if(a[i][j]=='#')pre=0,f[i][j]=f[i][j-1];
		else if(a[i][j]=='.')pre++,f[i][j]=max(f[i][j-1],pre);
		ans=max(ans,mx+f[i][m]);mx=max(mx,f[i][m]);
	}
	mx=0;
	for (int i=1;i<=m;i++){
		int pre=0;
		for (int j=1;j<=n;j++)
		if(a[j][i]=='#')pre=0,g[j][i]=g[j-1][i];
		else if(a[j][i]=='.')pre++,g[j][i]=max(g[j-1][i],pre);
		ans=max(ans,mx+g[n][i]);mx=max(mx,g[n][i]);
	}
	for (int i=1;i<=n;i++){
		int pre=0;
		for (int j=m;j>=1;j--)
		if(a[i][j]=='#')pre=0,ff[i][j]=ff[i][j+1];
		else if(a[i][j]=='.')pre++,ff[i][j]=max(ff[i][j+1],pre);
	}
	for (int i=1;i<=m;i++){
		int pre=0;
		for (int j=n;j>=1;j--)
		if(a[j][i]=='#')pre=0,gg[j][i]=gg[j+1][i];
		else if(a[j][i]=='.')pre++,gg[j][i]=max(gg[j+1][i],pre);
	}
	sf[n+1]=sg[m+1]=0;
	for (int i=1;i<=n;i++)
	pf[i]=max(pf[i-1],f[i][m]);
	for (int i=n;i>=1;i--)
	sf[i]=max(sf[i+1],f[i][m]);
	for (int i=1;i<=m;i++)
	pg[i]=max(pg[i-1],g[n][i]);
	for (int i=m;i>=1;i--)
	sg[i]=max(sg[i+1],g[n][i]);
//	cout<<ans<<"@@@@\n";
	for (int i=1;i<=n;i++){
		int pre=0,pp=0,p3=1;
		for (int j=1;j<=m;j++)
		if(a[i][j]=='#')pre=0,pp=0,p3=j+1;
		else if(a[i][j]=='.'){
			pre++,pp=max(max(pp,f[i-1][j]),ff[i+1][j]);
			ans=max(ans,max(pg[p3-1],max(max(sg[j+1],max(pf[i-1],sf[i+1])),pp))+j-p3+1);
		}
	}
//	cout<<ans<<"&&&&\n";
	for (int i=1;i<=m;i++){
		int pre=0,pp=0,p3=1;
		for (int j=1;j<=n;j++)
		if(a[j][i]=='#')pre=0,pp=0,p3=j+1;
		else if(a[j][i]=='.'){
			pre++,pp=max(max(pp,g[j][i-1]),gg[j][i+1]);
			ans=max(ans,max(pf[p3-1],max(max(sf[j+1],max(pg[i-1],sg[i+1])),pp))+j-p3+1);
		}
	}
	cout<<ans<<"\n";
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T;cin>>T;
	while(T--)solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 19ms
memory: 125404kb

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: 28ms
memory: 125412kb

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'