QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#563696#5414. Stop, Yesterday Please No MorexinlengweishangWA 6ms10176kbC++202.2kb2024-09-14 15:13:272024-09-14 15:13:28

Judging History

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

  • [2024-09-14 15:13:28]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:10176kb
  • [2024-09-14 15:13:27]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
map<char,int> gox,goy;
int mp[2020][2020],f[2020][2020];
void slove(){
    char s[100010];
	int n,m,k,ln,lm;
	scanf("%d%d%d",&n,&m,&k);
	scanf("%s",s);
	ln=n;
	lm=m;
	int len=strlen(s);
	int fx=1010,fy=1010,dx=1010,dy=1010;
	int maxx=1010,minx=1010,miny=1010,maxy=1010;
		mp[dy][dx]=1;
	for(int i=0;i<len;i++){
		char c=s[i];
		fx+=gox[c],fy+=goy[c];
		dx-=gox[c],dy-=goy[c];
		maxx=max(fx,maxx);
		minx=min(fx,minx);
		maxy=max(fy,maxy);
		miny=min(fy,miny);
		if(dx>=0&&dx<=2010&&dy>=0&&dy<=2010)
		mp[dy][dx]=1;
	}
	m-=(maxx-1010)+(1010-minx);
	n-=(maxy-1010)+(1010-miny);
	m=max(0,m);
	n=max(0,n);
	maxx=min(2010,maxx);
	maxy=min(2010,maxy);
	minx=max(10,minx);
	miny=max(10,miny);
	int ans=n*m-k;
//    printf("%d %d\n",m,n);
//    printf("%d %d %d %d\n",minx,maxx,miny,maxy);
	if(ans<0){
	for(int i=2020-maxy;i<=2020-miny;i++){
		for(int q=2020-maxx;q<=2020-minx;q++){
				mp[i][q]=0;
			}
		}
		printf("0\n");
		return ;
	}
	if(ans==0){
	for(int i=2020-maxy;i<=2020-miny;i++){
		for(int q=2020-maxx;q<=2020-minx;q++){
				mp[i][q]=0;
			}
		}
		printf("%d\n",ln*lm);
		return ;
	}
	/*
	printf("%d %d %d %d\n",maxy-1010,miny-1010,maxx-1010,minx-1010);
	for(int i=2020-maxy;i<=2020-miny;i++){
		for(int q=2020-maxx;q<=2020-minx;q++){
	        printf("%d %d mp:%d\n",i-1010,q-1010,mp[i][q]);
		}
	}
	*/
	for(int i=2020-maxy-1;i<=min(2010,2020-miny+n);i++){
		f[i][2020-maxx-1]=0;
	}
		for(int q=2020-maxx-1;q<=min(2010,2020-minx+m);q++){
			f[2020-maxy-1][q]=0;
		}
	for(int i=2020-maxy-1;i<=min(2010,2020-miny+n);i++){
		for(int q=2020-maxx-1;q<=min(2010,2020-minx+m);q++){
			f[i][q]=f[i-1][q]+f[i][q-1]-f[i-1][q-1];
			if(mp[i][q]) f[i][q]++,mp[i][q]=0;
//			printf("  %d %d %d\n",i-1010,q-1010,f[i][q]);
		}
	}
	int tt=0;
	for(int i=1010-n;i<=1010+n;i++){
		for(int q=1010-m;q<=1010+m;q++){
//			printf("%d %d %d\n",i-1010,q-1010,f[i][q]-f[i-n][q]-f[i][q-m]+f[i-n][q-m]);
			if(f[i][q]-f[i-n][q]-f[i][q-m]+f[i-n][q-m]==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;
	scanf("%d",&T);
	while(T--) slove();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 8116kb

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: 6ms
memory: 10176kb

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
7
15
45
240
10
0
0
2
10
18
2
14
42
39
17
9
2
2
3
121
8
57
24
8
0
6
6
9
6
5
320
6
7
7
5
9
16
0
14
20
4
10
21
22
22
51
12
6
6
5
10
48
28
8
12
13
15
7
3
5
10
8
14
44
0
5
6
0
4
30
14
21
105
11
11
17
9
66
5
11
28
30
10
21
9
5
10
90
7
8
14
3
48
26
11
5
0
30
5
4
7
7
29
18
12
13
0
17
7
7
0
72
0...

result:

wrong answer 5th numbers differ - expected: '18', found: '7'