QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#576261#5414. Stop, Yesterday Please No MorexinlengweishangTL 677ms7524kbC++201.7kb2024-09-19 19:41:392024-09-19 19:41:40

Judging History

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

  • [2024-09-19 19:41:40]
  • 评测
  • 测评结果:TL
  • 用时:677ms
  • 内存:7524kb
  • [2024-09-19 19:41:39]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
map<char,int> gox,goy;
void slove(){
	char s[100010];
	map<int,map<int,int> > mp,f;
	int dx=0,dy=0;
	int minx=0,maxx=0,miny=0,maxy=0,y,x,k;
	scanf("%d %d %d",&y,&x,&k);
	scanf("%s",s);
	mp[dy][dx]=1;
	for(int i=0;s[i]!='\0';i++){
		dx+=gox[s[i]];
		dy+=goy[s[i]];
		mp[-dy][-dx]=1;
		minx=min(minx,dx);
		maxx=max(maxx,dx);
		miny=min(miny,dy);
		maxy=max(maxy,dy);
//		printf("%d %d\n",-dy,-dx);
	}
	int ymax=y-maxy,ymin=-miny;
	int xmax=x-maxx,xmin=-minx;
	int ans=(ymax-ymin)*(xmax-xmin);
//	printf("%d %d %d %d\n",ymax,ymin,xmax,xmin);
	if((ymax-ymin)<=0||(xmax-xmin)<=0){
		if(k==0) printf("%d\n",x*y);
		else
		printf("0\n");
		return ;
	}
	ans-=k;
	if(ans<0){
		printf("0\n");
		return ;
	}
	int tt=0;
	for(int fy=-y+ymin-2;fy<=ymax;fy++){
		for(int fx=-x+xmin-2;fx<=xmax;fx++){
			f[fy][fx]=f[fy-1][fx]+f[fy][fx-1]-f[fy-1][fx-1];
			if(mp[fy][fx]) f[fy][fx]++;
//			printf("%d %d %d %d\n",fy,fx,mp[fy][fx],f[fy][fx]);
		}
	}
	for(int fy=0;fy<y;fy++){
		for(int fx=0;fx<x;fx++){
//			printf("f[%d][%d]=%d f[%d][%d]=%d ",-fy+ymax-1,-fx+xmax-1,f[-fy+ymax-1][-fx+xmax-1],-fy+ymax-1,-fx+xmin-1,f[-fy+ymax-1][-fx+xmin-1]);
//			printf("f[%d][%d]=%d f[%d][%d]=%d\n",-fy+ymin-1,-fx+xmax-1,f[-fy+ymin-1][-fx+xmax-1],-fy+ymin-1,-fx+xmin-1,f[-fy+ymin-1][-fx+xmin-1]);
			if(f[-fy+ymax-1][-fx+xmax-1]-f[-fy+ymax-1][-fx+xmin-1]-f[-fy+ymin-1][-fx+xmax-1]+f[-fy+ymin-1][-fx+xmin-1]==ans) tt++;
		}
	}
	printf("%d\n",tt);
	return ;
}

int main(){
	gox['U']=0,goy['U']=1;
	gox['D']=0,goy['D']=-1;
	gox['L']=-1,goy['L']=0;
	gox['R']=1,goy['R']=0;
	int T=1;
	scanf("%d",&T); 
	for(int i=1;i<=T;i++) slove();
	return 0;
	
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 677ms
memory: 7524kb

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: -100
Time Limit Exceeded

input:

1
1000 1000 979065
DDUULULUDULLULLDLUULURRLDURLRDLRRUURUUUDLRLUUDUUDUDLLDDDULU

output:


result: