QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#576222#5414. Stop, Yesterday Please No MorexinlengweishangWA 669ms7320kbC++201.7kb2024-09-19 19:28:512024-09-19 19:28:52

Judging History

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

  • [2024-09-19 19:28:52]
  • 评测
  • 测评结果:WA
  • 用时:669ms
  • 内存:7320kb
  • [2024-09-19 19:28:51]
  • 提交

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(ans<=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+xmin-1,-fx+xmax-1,f[-fy+xmin-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+xmin-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;
	
}

详细

Test #1:

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

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: -100
Wrong Answer
time: 669ms
memory: 7320kb

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:

4
11
20
126
0
15
35
240
15
0
0
13
16
18
16
16
1
17
108
4
0
2
3
4
7
28
16
18
0
9
10
9
0
5
320
9
0
3
0
0
12
0
13
0
0
14
0
22
34
51
23
2
6
4
1
48
28
8
36
22
35
0
6
4
108
13
18
44
0
14
9
0
4
30
14
77
105
12
16
17
0
66
10
11
28
56
34
60
11
8
56
90
14
8
110
3
48
30
26
10
0
30
5
10
3
8
15
63
27
36
0
36
0
1...

result:

wrong answer 1st numbers differ - expected: '228', found: '4'