QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#180506 | #5414. Stop, Yesterday Please No More | Zhou_JK | WA | 4ms | 10304kb | C++23 | 2.1kb | 2023-09-15 22:05:32 | 2023-09-15 22:05:33 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1005,L=1000005;
int n,m,k;
int len;
char s[L];
int a[N][N],sum[N][N];
int getsum(int l1,int r1,int l2,int r2)
{
l1=max(l1,1),r1=max(r1,1),l2=min(l2,n),r2=min(r2,m);
return sum[l2][r2]-sum[l1-1][r2]-sum[l2][r1-1]+sum[l1-1][r1-1];
}
void solve()
{
cin>>n>>m>>k;
string str;
cin>>str;
len=str.size();
for(int i=1;i<=len;i++)
s[i]=str[i-1];
int u=1,d=n,l=1,r=m;
int curu=1,curd=n,curl=1,curr=m;
for(int i=1;i<=len;i++)
{
if(s[i]=='U') curu++,curd++;
else if(s[i]=='D') curu--,curd--;
else if(s[i]=='L') curl++,curr++;
else if(s[i]=='R') curr--,curl--;
u=max(u,curu),d=min(d,curd),l=max(l,curl),r=min(r,curr);
}
if(u>d||l>r)
{
if(k==0) printf("%d\n",n*m);
else printf("0\n");
return;
}
int mnx=0,mny=0;
int curx=0,cury=0;
vector<pair<int,int>>pos;
pos.emplace_back(curx,cury);
for(int i=1;i<=n;i++)
{
if(s[i]=='U') curx--;
else if(s[i]=='D') curx++;
else if(s[i]=='L') cury++;
else if(s[i]=='R') cury--;
if(abs(curx)<d-u+1&&abs(cury)<r-l+1) pos.emplace_back(curx,cury);
mnx=min(mnx,curx),mny=min(mny,cury);
}
mnx=-mnx,mny=-mny;
mnx++,mny++;
sort(pos.begin(),pos.end());
pos.erase(unique(pos.begin(),pos.end()),pos.end());
for(auto &[x,y]:pos)
x+=mnx,y+=mny;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a[i][j]=0;
for(auto [x,y]:pos)
a[x][y]++;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
int ans=0;
for(int i=u;i<=d;i++)
for(int j=l;j<=r;j++)
if(getsum(mnx-(i-u),mny-(j-l),mnx+(d-i),mny+(r-j))==(d-u+1)*(r-l+1)-k) ans++;
cout<<ans<<"\n";
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
int T;
cin>>T;
while(T--)
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 7880kb
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: 4ms
memory: 10304kb
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:
1 1 7 0 6 0 0 1 7 0 0 0 14 9 4 1 1 2 0 0 0 2 4 0 7 10 2 5 8 0 0 0 24 3 0 11 10 0 6 14 1 12 0 1 2 0 1 1 13 4 2 0 0 9 1 8 0 1 11 5 1 0 8 13 15 0 11 5 7 1 0 12 0 1 16 1 0 2 7 20 2 0 5 1 1 0 19 0 2 0 0 0 10 12 0 7 14 80 7 2 3 13 14 0 0 3 1 4 12 0 0 0 1 14 1 11 0 10 8 0 12 13 0 0 0 1 78 2 0 0 1 3 0 13 10...
result:
wrong answer 1st numbers differ - expected: '228', found: '1'