QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#612458#5414. Stop, Yesterday Please No Moreice_cup#WA 5ms5964kbC++141.6kb2024-10-05 11:21:382024-10-05 11:21:44

Judging History

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

  • [2024-10-05 11:21:44]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:5964kb
  • [2024-10-05 11:21:38]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MID int mid=(l+r)>>1;
#define ls p<<1
#define rs p<<1|1
#define endl '\n'
int n,m,K,k;
string s;
vector<int>d[2010];
int dp[1010][1010],tmp[1010];
void clr(){
	for(int i=1000-n;i<=1000+n;i++)d[i].clear();
	for(int i=1;i<=n+3;i++){
		for(int j=1;j<=m+3;j++)dp[i][j]=0;
	}
}
void solve(){
	clr();
	cin>>n>>m>>K;
	cin>>s;
	k=s.size();
	int x=1000,y=1000;
	int x1=1,x2=n,y1=1,y2=m;
	d[x].push_back(y);
	for(int i=0;i<k;i++){
		if(s[i]=='U')x++;
		if(s[i]=='D')x--;
		if(s[i]=='L')y++;
		if(s[i]=='R')y--;
		if(x>=1000-n&&x<=1000+n)d[x].push_back(y);
		x1=max(x1,x-1000+1);
		x2=min(x2,1000-x+n);
		y1=max(y1,y-1000+1);
		y2=min(y2,1000-y+m);
		// cout<<x<<' '<<y<<endl;
	}
	// cout<<x1<<' '<<x2<<' '<<y1<<' '<<y2<<endl;
	for(int i=1000-n;i<=1000+n;i++){
		sort(d[i].begin(),d[i].end());
		int top=unique(d[i].begin(),d[i].end())-d[i].begin();
		for(int j=0;j<=m;j++)tmp[j]=0;
		for(int j=0;j<top;j++){
			int y=d[i][j]-1000;
			if(max(1,y1-y)>min(m,y2-y))continue;
			tmp[max(1,y1-y)]++;
			tmp[min(m,y2-y)+1]--;
		}
		for(int j=1;j<=m;j++)tmp[j]+=tmp[j-1];
		int x=i-1000;
		if(max(1,x1-x)>min(n,x2-x))continue;
		for(int j=1;j<=m;j++){
			dp[max(1,x1-x)][j]+=tmp[j];
			dp[min(n,x2-x)+1][j]-=tmp[j];
		}
	}
	int cnt=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			dp[i][j]+=dp[i-1][j];
			if(dp[i][j]==K)cnt++;
		}
	}
	cout<<cnt<<endl;
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int TTT;
	cin>>TTT;
	// TTT=1;
	while(TTT--)solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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
1
0
0
0
0
0
240
0
0
0
0
0
18
0
0
0
0
0
0
2
1
0
0
0
0
0
0
0
0
0
0
0
0
61
0
0
2
0
0
0
0
0
0
0
0
0
22
0
51
0
0
0
0
0
26
16
8
0
0
0
0
0
0
0
0
0
44
0
0
0
0
4
30
0
0
12
0
0
3
0
66
0
0
4
0
0
0
0
0
0
19
0
0
0
0
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
0
0
90
0
0
228
0
30
0
16
8...

result:

wrong answer 2nd numbers differ - expected: '11', found: '1'