QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#612537 | #5414. Stop, Yesterday Please No More | ice_cup# | WA | 0ms | 3660kb | C++14 | 1.7kb | 2024-10-05 11:49:44 | 2024-10-05 11:49:45 |
Judging History
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();
}
詳細信息
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'