QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#91616#4231. Rafting TripFHQYAC ✓20ms15364kbC++172.7kb2023-03-29 10:07:152023-03-29 10:07:19

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-29 10:07:19]
  • 评测
  • 测评结果:AC
  • 用时:20ms
  • 内存:15364kb
  • [2023-03-29 10:07:15]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=509;
int ans,res,f1,f2,p1,p2,p3,p4,xx,yy,pre,px,py,f;
int sign[maxn][maxn];
int mp[maxn][maxn];
int d[maxn][maxn];
//int pd[maxn][maxn];
int sx[4]={-1,0,1,0};
int sy[4]={0,1,0,-1};
int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x*f;
}
void write(int x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
bool check(int x,int y)
{
	if(mp[x][y]!=-1)
	{
		p1=mp[x][y];
		p2=(p1+2)%4;
		if(mp[x+sx[p1]][y+sy[p1]]==-1)
			return true;
	}
	return false;
}
void dfs1(int x,int y)
{
		if(sign[x][y])
			return;
	sign[x][y]=1;
	int bid[4];
	for(int t=0;t<4;t++)
	{
		bid[t]=d[x+sx[t]][y+sy[t]];
		d[x+sx[t]][y+sy[t]]=0;
		ans+=bid[t];
	}
	for(int t=0;t<4;t++)
	{
		p1=(t+2)%4;
		if(mp[x+sx[t]][y+sy[t]]==p1)
			dfs1(x+sx[t],y+sy[t]);
	}
	res=max(res,ans);
	for(int t=0;t<4;t++)
	{
		d[x+sx[t]][y+sy[t]]=bid[t];
		ans-=bid[t];
	}
	return;
}
void dfs2(int x,int y)
{
	//	if(d[x][y]==-1)
	//		return;
	if(sign[x][y])
	{
		f1=x;
		f2=y;
		return;
	}
	sign[x][y]=1;
	p1=mp[x][y];
	dfs2(x+sx[p1],y+sy[p1]);
	sign[x][y]=0;
	return;
}
void dfs3(int x,int y)
{
	sign[x][y]=1;
	if(x==f1&&y==f2&&f)
	{
		px=x;
		py=y;
		int st=0;
		while(st==0||(!(px==f1&&py==f2)))
		{
			st++;
			for(int t=0;t<4;t++)
			{
				if(!sign[px+sx[t]][py+sy[t]]&&mp[px+sx[t]][py+sy[t]]!=-1&&mp[px+sx[t]][py+sy[t]]==(t+2)%4)
				{
					dfs1(px+sx[t],py+sy[t]);
				}
			}
			int si=mp[px][py];
			px+=sx[si];
			py+=sy[si];
		}
		return;
	}
	f=1;
	p1=mp[x][y];
	int bid[4];
	for(int t=0;t<4;t++)
	{
		bid[t]=d[x+sx[t]][y+sy[t]];
		d[x+sx[t]][y+sy[t]]=0;
		ans+=bid[t];
	}
	dfs3(x+sx[p1],y+sy[p1]);
	res=max(res,ans);
	for(int t=0;t<4;t++)
	{
		d[x+sx[t]][y+sy[t]]=bid[t];
		ans-=bid[t];
	}
	return;
}
int main()
{
//	freopen("rand.out","r",stdin);
//	freopen("my.out","w",stdout);
	int a,b;
	res=0;
	cin>>a>>b;
	memset(mp,-1,sizeof(mp));
	for(int x=1;x<=a;x++)
	{
		string str;
		cin>>str;
		for(int t=1;t<=b;t++)
		{
			if(str[t-1]=='>')
				mp[x][t]=1;
			else if(str[t-1]=='^')
				mp[x][t]=0;
			else if(str[t-1]=='<')
				mp[x][t]=3;
			else if(str[t-1]=='v')
				mp[x][t]=2;
			else if(str[t-1]=='#')
				d[x][t]=1;
		}
		
	}
	for(int x=1;x<=a;x++)
	{
		for(int y=1;y<=b;y++)
		{
			if(check(x,y))
			{
				int bid[4];
				ans=0;
				dfs1(x,y);
				res=max(res,ans);
			}
		}
	}
	for(int x=1;x<=a;x++)
	{
		for(int y=1;y<=b;y++)
		{
			if(!sign[x][y]&&mp[x][y]!=-1)
			{
				dfs2(x,y);
				ans=0;
				f=0;
				dfs3(f1,f2);
			}
		}
	}
	cout<<res<<endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 5496kb

input:

5 6
v<<<#v
v#v<.>
>>v<<<
..v##^
#<<<.^

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 1ms
memory: 5496kb

input:

4 5
>v<<.
^<..#
#...#
.#>^#

output:

2

result:

ok single line: '2'

Test #3:

score: 0
Accepted
time: 3ms
memory: 5540kb

input:

4 6
>>v#>v
^#>>^v
^<<#v<
.#^<<#

output:

5

result:

ok single line: '5'

Test #4:

score: 0
Accepted
time: 0ms
memory: 4456kb

input:

6 6
^.>>>>
^.....
^....v
^....v
#....v
<<<<#v

output:

2

result:

ok single line: '2'

Test #5:

score: 0
Accepted
time: 2ms
memory: 5476kb

input:

6 7
^>>>>>v
^.....v
^.#^..v
^.#^<.v
^.....v
^<<<<<<

output:

2

result:

ok single line: '2'

Test #6:

score: 0
Accepted
time: 0ms
memory: 4480kb

input:

3 7
>v<<<<#
^<#####
#^<<<<<

output:

6

result:

ok single line: '6'

Test #7:

score: 0
Accepted
time: 2ms
memory: 5524kb

input:

3 5
><.v#
##.^#
...#.

output:

3

result:

ok single line: '3'

Test #8:

score: 0
Accepted
time: 2ms
memory: 4488kb

input:

7 3
###
#>#
###
...
###
#>.
###

output:

4

result:

ok single line: '4'

Test #9:

score: 0
Accepted
time: 2ms
memory: 4432kb

input:

2 2
>.
.#

output:

0

result:

ok single line: '0'

Test #10:

score: 0
Accepted
time: 2ms
memory: 4440kb

input:

2 2
..
.v

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 9ms
memory: 11540kb

input:

498 498
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<...

output:

41195

result:

ok single line: '41195'

Test #12:

score: 0
Accepted
time: 15ms
memory: 14368kb

input:

500 500
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...

output:

24926

result:

ok single line: '24926'

Test #13:

score: 0
Accepted
time: 13ms
memory: 15364kb

input:

500 500
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...

output:

24924

result:

ok single line: '24924'

Test #14:

score: 0
Accepted
time: 13ms
memory: 6664kb

input:

500 500
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...

output:

2056

result:

ok single line: '2056'

Test #15:

score: 0
Accepted
time: 17ms
memory: 6696kb

input:

500 500
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...

output:

970

result:

ok single line: '970'

Test #16:

score: 0
Accepted
time: 16ms
memory: 6612kb

input:

500 500
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...

output:

687

result:

ok single line: '687'

Test #17:

score: 0
Accepted
time: 14ms
memory: 6592kb

input:

500 500
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...

output:

481

result:

ok single line: '481'

Test #18:

score: 0
Accepted
time: 16ms
memory: 6540kb

input:

500 500
.>^v.^<<^<<<<<<....><v#....^.#.^..#.^<<<<#..#.><v.v..>>^<<..###..^<v..#>>>#.....^>^#.##.#......#.....#v#.>v.v#..##.#.^>>>>>v..#.v<..^...^..^#....#..>v.#^<..^^v..^.....vv..v...#^.v>>v#.#.#..#.v.^v<<......^#<.v...v>>^^<^#..^^v.^..^..^...#.#.^...^^<<<...##...v.........^.^.....>>>>>#.....><<<^.....

output:

13

result:

ok single line: '13'

Test #19:

score: 0
Accepted
time: 19ms
memory: 6444kb

input:

500 499
<<<<<#v.^.^v>v<^^.^<>><>^.^v.><^.v^<.^^#..v#>>><<<v^<>>^>>v<<<<^^^^#<>v>^<>>>^>^<<<#^^#v<<<<<<<<v>#v<<v^v.v^<<^<##><<^^<>^<#^^.^#>v^<<^>>>>v^.^>>^<#^>v^#<<<<^><^#.v^>^.^^v<.#^<<<v.v^^^#^<<.>^^#vvv<<^..>#v<.^<<<>>v>>>^.#v#>>#^<<^v<.>^#^.><^<>#^<<^^^^<<<<.><..><<#^<<>>>>>>>^^<>#>v<><#^^><v<><>...

output:

13

result:

ok single line: '13'

Test #20:

score: 0
Accepted
time: 19ms
memory: 6500kb

input:

499 500
v^^.#<^^^..>^.v^<^<<v>^<<^>^#^^v^.>vv<v.>v.^<<<<<.v.^>>v<^#v##<^<<<vv^^^^^.>^v...#>v#.#v^^>^<<>v>>v#<><v>#vv<>>v^.>v<^<v>^#>^<<<>^>v^^..vv<<<v#<<.^^<<.v^<>^<<v^<><<vvv#<<v.##^><vv^>^>^v^##>v>>>^^v.#>^.^.^#.v<<<<^#.^^<^^#.>v.#^<^^^..v<>v<.#.^.v#v^..#>v<vv<<<<<>#v^v.#>#..><>>^...^.#><^>>>>>>>>...

output:

12

result:

ok single line: '12'

Test #21:

score: 0
Accepted
time: 20ms
memory: 6428kb

input:

500 500
^v>>v>v<>>>^#>v<^<>>>>v<<<^v.>^><.v>v<>^>vv^v>>><.>^v>>#^<<<>^<vv^^>>>v<v.^^v>v<vv<^>vv^<<vv<^^^^>>^^<^>>^^>>#<v^>v>>^<v<#<<vv<<<<<<<<<<<<<<<<<<^^v>^^<^^^v^<<#><<><>^>^>>>v<>>v><<^^<v^v<>>>^<v>>^vv>>v>>>v>v.v.v<v>#^<<<<<<<<<<.>v>^<<<<><^v<>v#<.^>^>^vv.v<>^v#<##^v^>^#v<v<<<<>>>#^>v>>>>>v^^>>^...

output:

11

result:

ok single line: '11'

Test #22:

score: 0
Accepted
time: 8ms
memory: 6508kb

input:

500 500
######<##############^#####>########v##########v###############################<######<#####>######v########################v####v##########>######v####<##########^#<##################<#####<########v#######<^####^v#####################^v####>#########^###########.v####<##########v##########...

output:

10

result:

ok single line: '10'

Test #23:

score: 0
Accepted
time: 5ms
memory: 6464kb

input:

500 500
<^^<^>><##<v>^>>#<^>v<^v<^^^<<><^^^<^v<^<^^^v#v<<<vv<vv^>>>>>>><vv<<<<>vv^^<^^>><<^<^>^<>^><v>^>^vv>^>^><<^v>^<<>vvv><>>>>>^vv>>#<>>>^^<v<<<^>v^^^<#<<^v^<<>>>>><##^>>#<<<<<<<<^><<<<<<^v^vv.^><>v^^v<v^>vv#^<<<^<<>#>^>>v>^>^^<^>>>^<v<<<v#v^>^^^<^<>^^<vv<<<#>v<v<^v^#^^>>>>^v^^<<>>#>>v<<<<v^<vv>...

output:

14

result:

ok single line: '14'

Test #24:

score: 0
Accepted
time: 2ms
memory: 6400kb

input:

500 2
<v
.#
.#
vv
#<
v^
<>
<^
v.
#>
>#
v^
#<
^#
#<
>v
<>
^.
#.
<<
#<
>>
>#
>>
#<
#v
^#
<<
#^
#v
#^
^.
^#
v#
##
#>
<<
#^
v^
<v
^#
^>
>#
.v
#^
<#
##
.v
>#
##
^#
^<
^^
<#
.>
<^
v<
><
<v
#v
##
#>
#>
##
##
^#
v>
><
.^
v#
#^
v>
<v
##
##
#>
>v
#v
><
.#
#.
^#
#.
>#
v<
>#
#<
<^
^#
#.
<>
#^
.v
##
.v
.v
.#
>>
...

output:

6

result:

ok single line: '6'

Test #25:

score: 0
Accepted
time: 3ms
memory: 4476kb

input:

2 500
v##v#>>>>^>>#.##<<.>>^#.v^>^^>##^>^^##v^^#.^<#<###<##v#^>^^.v>v#<^<<##^#^.#<##>#>>#v#>^#vv.^v#>v.####.>#.>>v#<.>#^..#<v##>>>^#v###^<#^#<#^^#>v^>###>>>><#^#v>v.v<^.#v.v##<.####<<<^#>^#^#<#>v#>#>^#>##.>>>^^<##<^^<v<...#v#.#<>>>>#.##.v#<.##.^#<^>#<<vv^>^#^..#<^##^^#<<##.vv<v^#<><.#<<.^^##^.#<v.##...

output:

5

result:

ok single line: '5'

Test #26:

score: 0
Accepted
time: 8ms
memory: 14252kb

input:

500 500
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...

output:

31270

result:

ok single line: '31270'

Test #27:

score: 0
Accepted
time: 14ms
memory: 14304kb

input:

500 500
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...

output:

123584

result:

ok single line: '123584'

Test #28:

score: 0
Accepted
time: 12ms
memory: 6532kb

input:

500 500
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...

output:

331

result:

ok single line: '331'

Test #29:

score: 0
Accepted
time: 12ms
memory: 6536kb

input:

500 500
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...

output:

1234

result:

ok single line: '1234'

Test #30:

score: 0
Accepted
time: 8ms
memory: 6476kb

input:

500 500
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...

output:

281

result:

ok single line: '281'

Test #31:

score: 0
Accepted
time: 8ms
memory: 6468kb

input:

500 500
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...

output:

996

result:

ok single line: '996'