QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#671770#5414. Stop, Yesterday Please No Morehansue#WA 3ms19536kbC++203.2kb2024-10-24 14:23:292024-10-24 14:23:31

Judging History

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

  • [2024-10-24 14:23:31]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:19536kb
  • [2024-10-24 14:23:29]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

const int N = 1e3;
const int NM = 1e6;

	int n, m, k;
	
int c2t(char ch){
	if(ch == 'U')
		return 0;
	if(ch == 'D')
		return 1;
	if(ch == 'L')
		return 2;
	if(ch == 'R')
		return 3;
	return -1;
}

int rev(int t){
	return t ^ 1;
}

const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

	int s[N * 2 + 3][N * 2 + 3];

int sum(int stx, int sty, int edx, int edy){
	return s[edx][edy] - s[stx - 1][edy] - s[edx][sty - 1] + s[stx - 1][sty - 1];
}
	
void sol(){
	scanf("%d%d%d\n", &n, &m, &k);
	
//	printf("%d %d %d\n", n, m, k);
	
	char ch = getchar();
	int l = 0, dir;
	int delx, dely;
	int maxu, maxd, maxl, maxr;
	delx = dely = maxu = maxd = maxl = maxr = 0;
	
	int holx, holy;
	for(int i = 1; i <= n * 2; i++)
		for(int j = 1; j <= m * 2; j++)
			s[i][j] = 0;
	s[holx = n][holy = m] = 1;
	
	while(c2t(ch) >= 0){
		dir = c2t(ch);
		
//		printf("%d", dir);
		
		delx += dx[dir];
		dely += dy[dir];
		if(delx < 0)
			maxu = max(maxu, abs(delx));
		else 
			maxd = max(maxd, abs(delx));
		if(dely < 0)
			maxl = max(maxl, abs(dely));
		else 
			maxr = max(maxr, abs(dely));
		
		dir = rev(dir);
		holx += dx[dir];
		holy += dy[dir];
		if(1 <= holx && holx <= n * 2 && 1 <= holy && holy <= m * 2)
			s[holx][holy] = 1;
		
		ch = getchar();
	}
	
//	printf("\n");

	int stx = n + maxu, sty = m + maxl;
	int edx = n + n - 1 - maxd, edy = m + m - 1 - maxr;
	
//	printf("ud[%2d,%2d]  lr[%2d,%2d]\n", maxu, maxd, maxl, maxr);
//	printf("st[%2d,%2d]  ed[%2d,%2d]\n", stx, sty, edx, edy);
//	printf("%3c", ' ');
//	for(int i = 1; i <= m * 2; i++)
//		printf("%3d", i);
//	printf("\n");
//	for(int i = 1; i <= n * 2; i++){
//		printf("%3d", i);
//		for(int j = 1; j <= m * 2; j++)
//			printf("%3d", s[i][j]);
//		printf("\n");
//	}
//	printf("\n");
	
	if(maxu + maxd >= n || maxl + maxr >= m){
		if(k == 0)
			printf("%d\n", n * m);
		else 
			printf("0\n");
		return ;
	}
	
	for(int i = 1; i <= n * 2; i++)
		for(int j = 1; j <= m * 2; j++)
			s[i][j] = s[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
			
//	printf("%3c", ' ');
//	for(int i = 1; i <= m * 2; i++)
//		printf("%3d", i);
//	printf("\n");
//	for(int i = 1; i <= n * 2; i++){
//		printf("%3d", i);
//		for(int j = 1; j <= m * 2; j++)
//			printf("%3d", s[i][j]);
//		printf("\n");
//	}
//	printf("\n");
	
	int size = (edx - stx + 1) * (edy - sty + 1);
	int ans = 0;
	for(int p = 0; p <= n - 1; p++)
		for(int q = 0; q <= m - 1; q++)
			if(sum(stx - p, sty - q, edx - p, edy - q) == k){
//				printf("st(%2d,%2d)ed(%2d,%2d)\n", stx - p, sty - q, edx - p, edy - q);
//				printf("s[%2d][%2d]=%2d\n", edx - p, edy - q, s[edx - p][edy - q]);
//				printf("s[%2d][%2d]=%2d\n", stx - p - 1, edy - q, s[stx - p - 1][edy - q]);
//				printf("s[%2d][%2d]=%2d\n", edx - p, sty - q - 1, s[edx - p][sty - q - 1]);
//				printf("s[%2d][%2d]=%2d\n", stx - p - 1, sty - q - 1, s[stx - p - 1][sty - q - 1]);
				ans++;
			}
	
	printf("%d\n", ans);
	
}

int main(){
	memset(s, 0 , sizeof s);

	int T;
	scanf("%d", &T);
	while(T--)
		sol();

	return 0;

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 3ms
memory: 19532kb

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
0
0
0
15
0
240
0
0
0
0
0
18
0
0
0
0
0
0
2
2
3
0
0
0
0
0
0
0
0
9
9
0
320
0
0
3
0
0
0
0
0
0
0
0
0
22
0
51
0
10
6
0
0
48
28
8
0
0
0
0
0
0
0
0
0
44
0
0
0
0
4
30
0
0
105
0
0
17
0
66
0
11
28
0
0
0
0
0
0
90
0
0
0
6
48
0
0
0
0
30
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
48
0
0
225
0
0
0
0
11
0
90
0
0
228
0
...

result:

wrong answer 3rd numbers differ - expected: '20', found: '0'