QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#686311 | #5414. Stop, Yesterday Please No More | ucup-team3474 | WA | 3ms | 24564kb | C++20 | 2.1kb | 2024-10-29 11:02:53 | 2024-10-29 11:02:53 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1919810;
typedef long long ll;
typedef pair<ll,ll> PII;
int n,m,k;
int a[N],b[N];
char s[N];
ll c[2010][2010];
void add(int x,int y,int lenx,int leny){
int xx=x+lenx-1,yy=y+leny-1;
x=max(1,x),y=max(1,y);
xx=min(n,xx),yy=min(m,yy);
if(xx<=0||yy<=0) return;
c[x][y]++;
c[xx+1][yy+1]++;
c[xx+1][y]--;
c[x][yy+1]--;
}
void __(){
cin>>n>>m>>k;
int l=1,r=m,u=1,d=n;
scanf("%s",s+1);
int dx=0,dy=0;
int len=strlen(s+1);
for(int i=1;i<=len;i++){
if(s[i]=='U') u++;
else if(s[i]=='D') d--;
else if(s[i]=='L') l++;
else r--;
}
int leny=r-l+1,lenx=d-u+1;
int mn=0,mx=0,res=0;
for(int i=1;i<=len;i++){
if(s[i]=='U') res--;
else if(s[i]=='D') res++;
mn=min(mn,res),mx=max(mx,res);
}
// cout<<mn<<" "<<mx<<endl;
lenx=max(n-(mx-mn),0);
mn=0,mx=0,res=0;
for(int i=1;i<=len;i++){
if(s[i]=='L') res--;
else if(s[i]=='R') res++;
mn=min(mn,res),mx=max(mx,res);
}
// cout<<mn<<" "<<mx<<endl;
leny=max(m-(mx-mn),0);
ll tot=lenx*leny;
// cout<<lenx<<" "<<leny<<endl;
if(tot==0){
if(k==0) printf("%d\n",n*m);
else puts("0");
return;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) c[i][j]=0;
}
dx=u,dy=l;
// cout<<dx<<" "<<dy<<endl;
// int rx=u,ry=l;
add(dx,dy,lenx,leny);
for(int i=1;i<=len;i++){
if(s[i]=='D') dx++;
else if(s[i]=='U') dx--;
else if(s[i]=='R') dy++;
else dy--;
add(dx,dy,lenx,leny);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
c[i][j]+=(c[i-1][j]+c[i][j-1]-c[i-1][j-1]);
}
}
int ans=0;
// cout<<tot<<endl;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
// cout<<c[i][j]<<" ";
if(tot-c[i][j]==k) ans++;
}
// cout<<endl;
}
printf("%d\n",ans);
}
int main(){
int _=1;
cin>>_;
while(_--){
__();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5832kb
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: 3ms
memory: 24564kb
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 17 8 9 15 20 240 8 0 0 3 1 18 1 16 12 15 108 8 1 2 3 24 0 29 2 15 0 8 8 9 0 5 320 0 5 3 0 0 7 0 11 0 0 1 112 22 18 51 23 0 6 1 9 48 28 8 1 22 49 13 10 0 10 3 18 44 0 0 2 0 4 30 14 99 105 2 25 17 0 66 10 11 28 52 29 8 11 14 0 90 14 0 22 3 48 28 15 6 0 30 4 8 0 5 16 45 5 17 0 19 0 19 0 9 0 20 1...
result:
wrong answer 3rd numbers differ - expected: '20', found: '17'