QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#753025#5414. Stop, Yesterday Please No MoreHHSAC ✓661ms21048kbC++141.6kb2024-11-16 10:59:562024-11-16 10:59:57

Judging History

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

  • [2024-11-16 10:59:57]
  • 评测
  • 测评结果:AC
  • 用时:661ms
  • 内存:21048kb
  • [2024-11-16 10:59:56]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,k;
ll t;
ll cha[1002][1002];
ll st[1002][1002];
void solve()
{
	cin>>n>>m>>k;
	memset(cha,0,sizeof cha);
	memset(st,0,sizeof st);
	string str;
	cin>>str;
	ll chui=0,shui=0;
	ll p1=0,p2=0,p3=0,p4=0;
	for(auto x:str)
	{
		if(x=='U')
			chui++;
		else if(x=='D')
			chui--;
		else if(x=='L')
			shui++;
		else 
			shui--;
		if(chui>0)
			p1=max(p1,chui);
		else if(chui<0)
			p2=max(p2,(-chui));
	    if(shui>0)
			p3=max(p3,shui);
		else if(shui<0)
			p4=max(p4,(-shui));
		
	}
	p1=1+p1;p2=n-p2;p3=1+p3;p4=m-p4;
	ll len1=p2-p1+1;
	ll len2=p4-p3+1;
	ll x=p1,y=p3;
//	cout<<x<<" "<<y<<endl;
//	cout<<len1<<" "<<len2<<endl;
	if(len1<=0||len2<=0)
	{
		if(k==0)
			cout<<n*m<<endl;
		else cout<<0<<endl;
		return ;
	}
	cha[x][y]++;
	cha[x+len1][y]--;
	cha[x][y+len2]--;
	cha[x+len1][y+len2]++;
	st[x][y]=1;
	for(auto s:str)
	{
		if(s=='U')
			x--;
		else if(s=='D')
			x++;
		else if(s=='L')
			y--;
		else 
			y++;
		if(st[x][y])continue;
		st[x][y]=1;
		cha[x][y]++;
		cha[x+len1][y]--;
		cha[x][y+len2]--;
		cha[x+len1][y+len2]++;
	//	cout<<x<<" "<<y<<endl;
	}
	for(ll i=1;i<=n;i++)
	{
		for(ll j=1;j<=m;j++)
		{
			cha[i][j]+=cha[i-1][j];
			cha[i][j]+=cha[i][j-1];
			cha[i][j]-=cha[i-1][j-1];
		}
	}
	ll cnt=0;
	ll ans=len1*len2-k;
//	cout<<ans<<endl;
	for(ll i=1;i<=n;i++)
	{
		for(ll j=1;j<=m;j++)
		{
			if(cha[i][j]==ans)
				cnt++;
		//	cout<<cha[i][j]<<" ";
		}
	//	cout<<endl;
	}
	cout<<cnt<<endl;
	//cout<<p1<<" "<<p2<<" "<<p3<<" "<<p4<<endl;
}
int main()
{
	cin>>t;
	while(t--)
	{
		solve();
	}
}

详细

Test #1:

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

input:

3
4 5 3
ULDDRR
4 5 0
UUUUUUU
4 5 10
UUUUUUU

output:

2
20
0

result:

ok 3 number(s): "2 20 0"

Test #2:

score: 0
Accepted
time: 661ms
memory: 19244kb

input:

1060
19 12 0
UDLDDUUUUDDDLLRDUDUURULUUUDRDUDRDRLRLRLULULLLDLDDRLUUUURUUUDDRLLRUUUDULURUULLRDRLRDDURDUUURRRLURLRUULRRUDURDLUUURDLURDDLUUURDDRLLURRDLRUDLRDRLLRRDRDDLDRURRRLUDULLLRUUDLRRURRDLLRRRDLLRDDDLRLRURURDDDL
11 1 0
UR
3 18 33
UDRLR
17 11 132
RLDRDLDRUU
6 10 13
UULUDDLRDLUUDLDD
1 15 0
D
6 20 50
D...

output:

228
11
20
99
18
15
34
240
15
0
0
13
14
18
26
16
1
19
108
8
2
2
3
7
0
30
16
21
0
8
10
9
15
5
320
11
7
3
0
0
12
0
11
0
0
14
0
22
36
51
23
7
6
4
2
48
28
8
63
22
49
13
10
4
108
10
18
44
0
15
9
0
4
30
14
99
105
10
14
17
0
66
10
11
28
52
34
56
33
14
56
90
14
0
121
3
48
30
36
13
0
30
7
8
3
11
16
45
20
34
0...

result:

ok 1060 numbers

Test #3:

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

input:

1
1000 1000 979065
DDUULULUDULLULLDLUULURRLDURLRDLRRUURUUUDLRLUUDUUDUDLLDDDULU

output:

958416

result:

ok 1 number(s): "958416"

Test #4:

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

input:

1
1000 1000 943471
LRLDLURLDLRDRDUULULRDDLLRURDUURLLDDLDLDDLLLUUURLDRUDRLLUUUUUDLUUDLURURRDLRLRRRLULRRULURLRRDLDRLUDRRLDDLUDRRLLUDLLLRDULRRRRLDUUDRDLULUUUUDRRDULUDLLUUDLDURDRRLRRLDRLDDRURURLUULRRLDLLRLRDRRUULDLDLULLDLLRULLRUULURDURRLUUDUULLULDLRUDDLRLRLLUDDDLLLUDRRLDDULRRURRDURDDRDLLULRLULURLRDLLURD...

output:

889224

result:

ok 1 number(s): "889224"

Test #5:

score: 0
Accepted
time: 23ms
memory: 21048kb

input:

1
1000 1000 315808
LLRURURRDDDULLDDUDRDLRLLLDDDLUDRDURLDULRLRULUUDLUULUUDULLLLDDURLDUULUUDLLDLLDRUDUULRLLRLRUURLRLULLDDLLDUDLLRUUDRLDLUULDLLDRRRURDULLDRRRDURURDRLDURURUDLURLDURRLRRUDUDURDRLRRRDLRRURLURUDRRLDLRULLDLUURDURLURLLRDLRDRUURURDRUDUUUDLRRLUDLUUDUDDRRDUULUUDDRLLULDUUDRURRDRLULRLULDURLURUDLLD...

output:

426

result:

ok 1 number(s): "426"

Test #6:

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

input:

1
1000 1000 986018
LLULDRRRDDURRUDRUURRRDDLUUDUULRULRDULLD

output:

972180

result:

ok 1 number(s): "972180"

Test #7:

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

input:

1
1000 1000 945431
DDRRURUUDLDULLDLDDLRULDLLDDRRLUDRLUURRLDRDLURUURRRRLRURLURULLLDRDDDRRRLDLDRLRDDUURRURDDDLRUURLUURLRDUDDDLLDUURLDLUDLLRRDUUDRLUULLUULDLURRUDLUURLRLRURDUDRRRDRLRUDLLLLURLULRLRLRRDDUDLRLDUUUULUDLLURRLURRDLRURRRULDDLLLRLRDLUDLLDDRULDUULRDDUUDDUDLURDULLDUDDLULRULDRLDDULDULLUDLULUDRURRR...

output:

893000

result:

ok 1 number(s): "893000"

Test #8:

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

input:

1
1000 1000 460035
RDDUURDULDDLDDLDDLDRRULLRLUURLURRRDRUDDDRDLDLDULUDLRLLRRLRRURRRDLRLUDRDURULDRRDDDDDDLRLDULUULDUDRLLUUUURUUDRURLRRULDRDRUUUUULULRURDDRLRULLLRDRRULUDDUDDLLLRDRUULUUDDRLURDLDURRDLRRLDRRUDLUULRDLURULLDLRLLDDURDUDLDULDLLRULRDLRLUULLUDRUDDDLRRDULULLRUURLUURRLLLLRLDRURLLRLDRRDDDRLUUUUDUL...

output:

417

result:

ok 1 number(s): "417"

Test #9:

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

input:

1
1000 1000 992010
LLLLLDLDRRLUDRR

output:

1999

result:

ok 1 number(s): "1999"

Test #10:

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

input:

1
1000 1000 919600
LLDLRUDRLURRUDRDRRDLRUDLRRRUUULDLDURDDDRUURRRLLURULDRLRLULLULDRULULRLRRRURLDDDRUUULUDLLLLRRLLRDDRDULUDLRLRLDRLUDUDURRULUULLDULUULDLLDRDULUDLDULDDUULDDRRURDRDULRRLDRRDUURURRLUUUDRRLDRRDDLULRDDLDLLRLRLLLRULUUUURRRLDLRUDRRLRURDRLDULLLUDRULLDLDRRUUDLRRLLRLDDLUDLRLRRURUUDUULUDURDURRLUU...

output:

944

result:

ok 1 number(s): "944"

Test #11:

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

input:

1
1000 1000 804351
DLRLDLLLLUDRDURRLDDRRLRUULURURDDDRDLRUDDULRRLLULURDRUUDRURRLURRRDRURRDRLULRDLRRDRRDDUDLUDLDULRUURRLRUUDRLDDRDDUUDULUULUUUDLRURULLRDUUDDDRRLDRUDDUUDRURLRDRUDLRLDDRRLLRLRDUDDULLULRLLDDUDDDUULDULLRRULULDUUULUDRRDRLUDLRRDDUDLRRDDLDLDRUULRRRRRLRLULLRDDRDDDULDRRURUDDLURLRLURLRDRULUDULUU...

output:

640000

result:

ok 1 number(s): "640000"