QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#364601#5414. Stop, Yesterday Please No Moreucup-team3294#WA 3ms3920kbC++231.7kb2024-03-24 15:35:232024-03-24 15:35:24

Judging History

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

  • [2024-03-24 15:35:24]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3920kb
  • [2024-03-24 15:35:23]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+5;
void solve() {
	int n,m,k,count=0;
	cin>>n>>m>>k;
	string a;
	cin>>a;
	int l1=1,r1=n,l2=1,r2=m,l1min=1,r1max=n,l2min=1,r2max=m;
	for(int i=0; i<a.size(); i++) {
		if(a[i]=='U') {
			l1--,r1--;
			l1min=min(l1,l1min);
			r1max=max(r1max,r1);
		} else if(a[i]=='D') {
			l1++,r1++;
			l1min=min(l1,l1min);
			r1max=max(r1max,r1);
		} else if(a[i]=='L') {
			l2--,r2--;
			l2min=min(l2,l2min);
			r2max=max(r2max,r2);
		} else {
			l2++,r2++;
			l2min=min(l2,l2min);
			r2max=max(r2max,r2);
		}
	}
	int x1=2-l1min,x2=n-(r1max-n),y1=2-l2min,y2=m-(r2max-m);
	if(x1>x2||y1>y2) {
		if(k) cout<<0<<"\n";
		else cout<<n*m<<"\n";
	} else {
		int p=(x2-x1+1)*(y2-y1+1);
		vector<vector<int>> d(n+10,vector<int>(m+10));
		string s=a;
		for(int i=0; i<s.size(); i++) {
			d[x1][y1]++;
			d[x2+1][y1]--;
			d[x1][y2+1]--;
			d[x2+1][y2+1]++;
			if(s[i]=='U') x1--,x2--;
			else if(s[i]=='D') x1++,x2++;
			else if(s[i]=='L') y1--,y2--;
			else y1++,y2++;
		}
		d[x1][y1]++;
		d[x2+1][y1]--;
		d[x1][y2+1]--;
		d[x2+1][y2+1]++;
		vector<vector<int>> c(n+10,vector<int>(m+10));
		c[1][1]=d[1][1];
		for(int i=2; i<=m; i++) c[1][i]=d[1][i]+c[1][i-1];
		for(int i=2; i<=n; i++) c[i][1]=d[i][1]+c[i-1][1];
		for(int i=2; i<=n; i++) {
			for(int j=2; j<=m; j++) {
				c[i][j]=d[i][j]+c[i-1][j]+c[i][j-1]-c[i-1][j-1];
			}
		}
		int sum=0;
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=m; j++) {
				//cout<<c[i][j]<<" ";
				if(c[i][j]==p-k) sum++;
			}
			//cout<<endl;
		}
		cout<<sum<<"\n";
	}
}
signed main() {
	int T=1;
	cin>>T;
	while(T--) {
		solve();
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 3920kb

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
17
9
18
15
21
240
14
0
0
5
1
18
3
16
1
31
108
8
1
2
3
7
0
29
4
20
0
8
10
9
6
5
320
3
5
3
0
0
7
0
11
0
0
8
128
22
18
51
23
5
6
3
9
48
28
8
1
22
49
13
10
2
12
6
18
44
0
14
5
0
4
30
14
99
105
2
27
17
0
66
10
11
28
52
32
8
22
14
0
90
15
0
22
3
48
29
20
9
0
30
6
8
3
10
16
45
16
17
0
20
0
21
0
6
0
...

result:

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