QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#563755#5414. Stop, Yesterday Please No MorexinlengweishangTL 3ms35892kbC++202.5kb2024-09-14 15:45:472024-09-14 15:45:48

Judging History

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

  • [2024-09-14 15:45:48]
  • 评测
  • 测评结果:TL
  • 用时:3ms
  • 内存:35892kb
  • [2024-09-14 15:45:47]
  • 提交

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];
    for(int i=0;i<2020;i++){
    	for(int q=0;q<2020;q++){
    		mp[i][q]=0;
    		f[i][q]=0;
		}
	}
	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\n",ans);
//    printf("m=%d n=%d\n",m,n);
//    printf("minx %d maxx %d miny %d maxy %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=max(0,2020-maxy-1);i<=min(2010,2020-miny+n+2);i++){
		for(int q=max(0,2020-maxx-1);q<=min(2010,2020-minx+m+2);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=max(n,2020-maxy-1);i<=min(2010,2020-miny+n+2);i++){
		for(int q=max(m,2020-maxx-1);q<=min(2010,2020-minx+m+2);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;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 35892kb

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

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:


result: