QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#250584#5414. Stop, Yesterday Please No Morecscnk52TL 8ms17668kbC++142.4kb2023-11-13 13:38:592023-11-13 13:38:59

Judging History

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

  • [2023-11-13 13:38:59]
  • 评测
  • 测评结果:TL
  • 用时:8ms
  • 内存:17668kb
  • [2023-11-13 13:38:59]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e3 + 7;

int sum[N<<1][N<<1];
int tag[N<<1][N<<1];
const int M=1e3+5;
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int t = 1;
	cin >> t;
	while (t--) {
		int n, m, k;
		cin >> n >> m >> k;
		string s;
		cin >> s;
		int slen = s.length();
		int max_L=0 , max_R=0 , max_U=0 , max_D=0 , x=0 , y=0;
		for(int i=0;i<slen;i++)
		{
			if(s[i]=='L') y--;
			if(s[i]=='R') y++;
			if(s[i]=='U') x--;
			if(s[i]=='D') x++;
			max_L=max(min(max_L , y) , -m);
			max_R=min(max(max_R , y) , m);
			max_U=max(min(max_U , x) , -n);
			max_D=min(max(max_D , x) , n);
		}
//		cout<<max_L<<" "<<max_R<<" "<<max_U<<" "<<max_D<<endl;
		int now_Ux=abs(max_U);
		int now_Dx=n-1-max_D;
		int now_Ly=abs(max_L);
		int now_Ry=m-1-max_R;
//		cout<<"now_Ux="<<now_Ux<<" now_Dx="<<now_Dx<<" now_Lx="<<now_Ly<<" now_Rx="<<now_Ry<<endl;
		int now_num=(now_Ry-now_Ly+1)*(now_Dx-now_Ux+1);
		int holl_x=M , holl_y=M;
		now_Ly+=M;
		now_Ry+=M;
		now_Dx+=M;
		now_Ux+=M;
		tag[holl_x][holl_y]=1;
		for(int i=0;i<(int)s.size();i++)
		{
			if(s[i]=='L') holl_y++;
			if(s[i]=='R') holl_y--;
			if(s[i]=='U') holl_x++;
			if(s[i]=='D') holl_x--;
			tag[holl_x][holl_y]=1;
		}
//		for(int i=M-10;i<(M+n);i++)
//			{
//				for(int j=M-10;j<(M+m);j++)
//					cout<<tag[i][j]<<" ";
//				cout<<endl;
//			}		
//		cout<<endl;
		for(int i=1;i<=(M+n);i++)
			for(int j=1;j<=(M+m);j++)
			{
				if(sum[i][j]!=0) sum[i][j]=0;
				sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+tag[i][j];
			}		
		int xx=M , yy=M;
		for(int i=0;i<slen;i++)
		{
			if(s[i]=='L') yy++;
			if(s[i]=='R') yy--;
			if(s[i]=='U') xx++;
			if(s[i]=='D') xx--;
			tag[xx][yy]=0;
		}		
		int ans=0;
//		for(int i=M;i<(M+n);i++)
//			{
//				for(int j=M;j<(M+m);j++)
//					cout<<sum[i][j]<<" ";
//				cout<<endl;
//			}
//		cout<<endl;
//		
//		for(int i=M-10;i<(M+n);i++)
//			{
//				for(int j=M-10;j<(M+m);j++)
//					cout<<sum[i][j]<<" ";
//				cout<<endl;
//			}
//		
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				int real_dx=now_Dx-i;
				int real_ux=now_Ux-i;
				int real_ly=now_Ly-j;
				int real_ry=now_Ry-j;
				int cnt_x=sum[real_dx][real_ry]-sum[real_ux-1][real_ry]-sum[real_dx][real_ly-1]+sum[real_ux-1][real_ly-1];
				
				if(now_num-cnt_x==k) ans++;
			}
		}
		cout<<ans<<endl;

	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 8ms
memory: 17668kb

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: