QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#618937#5414. Stop, Yesterday Please No MoresazhiWA 7ms3776kbC++202.2kb2024-10-07 11:58:152024-10-07 11:58:16

Judging History

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

  • [2024-10-07 11:58:16]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:3776kb
  • [2024-10-07 11:58:15]
  • 提交

answer

// author:  jieda
// file:	cpp
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
# define fi first
# define se second
# define all(x) x.begin(),x.end()
# define stst stringstream
# define pb push_back
# define pf push_front
# define pp push
# define lowbit(x) (x)&(-x)
# define fa(i,op,n) for (int i = op; i <= n; i++)
# define fb(j,op,n) for (ll j = op; j >= n; j--)
# define fg(i,op,n) for (ll i = op; i != n; i = ne[i])
int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};
typedef unsigned long long  ull;
typedef long long ll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const ll N = 2e5+10,INF = 0x3f3f3f3f,mod = 1e9+7;
const ll MOD = 212370440130137957ll;//hash(hight)
const int base = 131;
const double eps = 1e-3;
const int seed=10086,mo=1e6+7; //hash(lower)
int prime = 233317;
void solve(){
	int n,m,k;cin>>n>>m>>k;
	string s;cin>>s;s = " "+s;int M = s.size()-1;
	int U = 1,D = n,L = 1,R = m;
	for(int i = 1,u = 1,d = n,l = 1,r = m;i<=M;i++){
		if(s[i] == 'U') u++,d++;
		if(s[i] == 'D') u--,d--;
		if(s[i] == 'L') l++,r++;
		if(s[i] == 'R') l--,r--;
		U = max(u,U);
		D = min(d,D);
		L = max(l,L);
		R = min(r,R);
	}
	if(k == 0){
	    cout<<n*m<<'\n';
	    return ;
	}
	if(U>D||L>R){
		cout<<0<<'\n';
		return ;
	}
	int delt = (D-U+1)*(R-L+1)-k;
	vector<vector<int>> f(2*n+5,vector<int>(2*m+5));
	f[n+1][m+1] = 1;
	for(int i = 1,x = n+1,y = m+1;i<=M;i++){
		if(s[i] == 'U') x++;
		else if(s[i] == 'D') x--;
		else if(s[i] == 'L') y++;
		else if(s[i] == 'R') y--;
		f[x][y] = 1;
	} 
	for(int i = 1;i<=2*n+1;i++){
		for(int j = 1;j<=2*m+1;j++){
			f[i][j] += f[i][j-1];
		}
	}
	for(int i = 1;i<=2*n+1;i++){
		for(int j = 1;j<=2*m+1;j++){
			f[i][j] += f[i-1][j];
		}
	}
	ll ans = 0;
	int x = n+1,y = m+1;
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=m;j++){
			int nowx= x-i,nowy = y-j;
			int res = f[D+nowx][R+nowy]-f[U-1+nowx][R+nowy]-f[D+nowx][L-1+nowy]+f[U-1+nowx][L-1+nowy];
			if(res == delt) ans++;
		}
	}
 	cout<<ans<<'\n';

}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int t = 1;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}
/*

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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
18
15
34
240
15
0
0
13
14
18
26
16
1
19
108
8
2
2
3
7
0
30
16
21
0
8
10
9
15
5
320
11
7
3
0
0
12
0
11
0
0
14
0
22
36
51
23
7
6
4
2
48
28
8
63
22
49
13
10
4
108
10
18
44
0
15
9
0
4
30
14
99
105
10
14
17
0
66
10
11
28
52
34
56
33
14
56
90
14
0
121
3
48
30
36
13
0
30
7
8
3
11
16
45
20
34
0...

result:

wrong answer 606th numbers differ - expected: '1', found: '24'