QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#612537#5414. Stop, Yesterday Please No Moreice_cup#WA 0ms3660kbC++141.7kb2024-10-05 11:49:442024-10-05 11:49:45

Judging History

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

  • [2024-10-05 11:49:45]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3660kb
  • [2024-10-05 11:49:44]
  • 提交

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,x-1000+n);
		y1=max(y1,y-1000+1);
		y2=min(y2,y-1000+m);
		// cout<<x<<' '<<y<<endl;
	}
	// cout<<x1<<' '<<x2<<' '<<y1<<' '<<y2<<endl;
	K=(x2-x1+1)*(y2-y1+1)-K;
	for(int i=1000-n;i<=1000+n;i++){
		if(!d[i].size())continue;
		sort(d[i].begin(),d[i].end());
		int top=unique(d[i].begin(),d[i].end())-d[i].begin();
		// cout<<top<<' '<<d[i].size()<<endl;
		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]--;
		}
		// cout<<endl;
		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];
			// cout<<dp[i][j]<<' ';
			if(dp[i][j]==K)cnt++;
		}
		// cout<<endl;
	}
	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: 0
Wrong Answer
time: 0ms
memory: 3660kb

input:

3
4 5 3
ULDDRR
4 5 0
UUUUUUU
4 5 10
UUUUUUU

output:

2
0
0

result:

wrong answer 2nd numbers differ - expected: '20', found: '0'