QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#176576 | #5414. Stop, Yesterday Please No More | brz | AC ✓ | 23ms | 20116kb | C++20 | 1.9kb | 2023-09-11 19:58:30 | 2023-09-11 19:58:30 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define cn getchar
template<class TY>void read(TY &x){
x=0;int f1=1;char ch=cn();
while(ch<'0'||ch>'9'){if(ch=='-')f1=-1;ch=cn();}
while(ch>='0'&&ch<='9')x=x*10+(ch-'0'),ch=cn(); x*=f1;
}
template<class TY>void write2(TY x){
if(x>9)write2(x/10);
putchar(x%10+'0');
}
template<class TY>void write(TY x){
if(x<0)putchar('-'),x=-x;
write2(x);
}
int n,m,k,len;
int sum[2010][2010];
char s[1000010];
int main()
{
int Te;read(Te);while(Te--){
read(n); read(m); read(k);
char ch = getchar(); len=0;
while(ch<'A' || ch>'Z')ch = getchar();
while(ch>='A' && ch<='Z')s[++len] = ch,ch=getchar();
for(int i=1;i<=2*n;i++)
for(int j=1;j<=2*m;j++)
sum[i][j]=0;
int mi1=0,ma1=0,mi2=0,ma2=0;
int x=0,y=0;
for(int i=1;i<=len;i++){
if(s[i]=='U')x--;
if(s[i]=='D')x++;
if(s[i]=='L')y--;
if(s[i]=='R')y++;
mi1=min(mi1,x);
ma1=max(ma1,x);
mi2=min(mi2,y);
ma2=max(ma2,y);
}
int a=0,b=0,c=0,d=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(i+mi1>=1 && i+ma1<=n && j+mi2>=1 && j+ma2<=m){
if(!a)a=i,b=j;
c=i,d=j;
}
}
// printf("%d %d %d %d\n",a,b,c,d);
if(a==0){
if(!k)write(n*m),puts("");
else puts("0");
continue;
}
x=n+1,y=m+1;
int X=c-a+1,Y=d-b+1;
sum[x][y]=1;
// printf("x y : %d %d\n",x,y);
for(int i=1;i<=len;i++){
if(s[i]=='U')x++;
if(s[i]=='D')x--;
if(s[i]=='L')y++;
if(s[i]=='R')y--;
if(x>=1 && x<=2*n && y>=1 && y<=2*m)sum[x][y]=1;
// printf(": %d %d\n",x,y);
}
for(int i=1;i<=2*n;i++)
for(int j=1;j<=2*m;j++)
sum[i][j]+=sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
int ans=0;
for(int i=c+1;i<=c+n;i++)
for(int j=d+1;j<=d+m;j++){
int p=sum[i][j] - sum[i-X][j] - sum[i][j-Y] + sum[i-X][j-Y];
if(X*Y - p == k)ans++;//,printf("%d %d\n",i,j);
}
write(ans);puts("");
}
}
/*
1
3 3 3
DR
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3552kb
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: 0
Accepted
time: 2ms
memory: 6204kb
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 20 99 18 15 34 240 15 0 0 13 14 18 26 16 1 19 108 8 2 2 3 7 0 30 16 21 0 8 10 9 15 5 320 11 7 3 0 0 12 0 11 0 0 14 0 22 36 51 23 7 6 4 2 48 28 8 63 22 49 13 10 4 108 10 18 44 0 15 9 0 4 30 14 99 105 10 14 17 0 66 10 11 28 52 34 56 33 14 56 90 14 0 121 3 48 30 36 13 0 30 7 8 3 11 16 45 20 34 0...
result:
ok 1060 numbers
Test #3:
score: 0
Accepted
time: 4ms
memory: 19144kb
input:
1 1000 1000 979065 DDUULULUDULLULLDLUULURRLDURLRDLRRUURUUUDLRLUUDUUDUDLLDDDULU
output:
958416
result:
ok 1 number(s): "958416"
Test #4:
score: 0
Accepted
time: 4ms
memory: 19088kb
input:
1 1000 1000 943471 LRLDLURLDLRDRDUULULRDDLLRURDUURLLDDLDLDDLLLUUURLDRUDRLLUUUUUDLUUDLURURRDLRLRRRLULRRULURLRRDLDRLUDRRLDDLUDRRLLUDLLLRDULRRRRLDUUDRDLULUUUUDRRDULUDLLUUDLDURDRRLRRLDRLDDRURURLUULRRLDLLRLRDRRUULDLDLULLDLLRULLRUULURDURRLUUDUULLULDLRUDDLRLRLLUDDDLLLUDRRLDDULRRURRDURDDRDLLULRLULURLRDLLURD...
output:
889224
result:
ok 1 number(s): "889224"
Test #5:
score: 0
Accepted
time: 20ms
memory: 20104kb
input:
1 1000 1000 315808 LLRURURRDDDULLDDUDRDLRLLLDDDLUDRDURLDULRLRULUUDLUULUUDULLLLDDURLDUULUUDLLDLLDRUDUULRLLRLRUURLRLULLDDLLDUDLLRUUDRLDLUULDLLDRRRURDULLDRRRDURURDRLDURURUDLURLDURRLRRUDUDURDRLRRRDLRRURLURUDRRLDLRULLDLUURDURLURLLRDLRDRUURURDRUDUUUDLRRLUDLUUDUDDRRDUULUUDDRLLULDUUDRURRDRLULRLULDURLURUDLLD...
output:
426
result:
ok 1 number(s): "426"
Test #6:
score: 0
Accepted
time: 4ms
memory: 19160kb
input:
1 1000 1000 986018 LLULDRRRDDURRUDRUURRRDDLUUDUULRULRDULLD
output:
972180
result:
ok 1 number(s): "972180"
Test #7:
score: 0
Accepted
time: 4ms
memory: 19588kb
input:
1 1000 1000 945431 DDRRURUUDLDULLDLDDLRULDLLDDRRLUDRLUURRLDRDLURUURRRRLRURLURULLLDRDDDRRRLDLDRLRDDUURRURDDDLRUURLUURLRDUDDDLLDUURLDLUDLLRRDUUDRLUULLUULDLURRUDLUURLRLRURDUDRRRDRLRUDLLLLURLULRLRLRRDDUDLRLDUUUULUDLLURRLURRDLRURRRULDDLLLRLRDLUDLLDDRULDUULRDDUUDDUDLURDULLDUDDLULRULDRLDDULDULLUDLULUDRURRR...
output:
893000
result:
ok 1 number(s): "893000"
Test #8:
score: 0
Accepted
time: 23ms
memory: 20108kb
input:
1 1000 1000 460035 RDDUURDULDDLDDLDDLDRRULLRLUURLURRRDRUDDDRDLDLDULUDLRLLRRLRRURRRDLRLUDRDURULDRRDDDDDDLRLDULUULDUDRLLUUUURUUDRURLRRULDRDRUUUUULULRURDDRLRULLLRDRRULUDDUDDLLLRDRUULUUDDRLURDLDURRDLRRLDRRUDLUULRDLURULLDLRLLDDURDUDLDULDLLRULRDLRLUULLUDRUDDDLRRDULULLRUURLUURRLLLLRLDRURLLRLDRRDDDRLUUUUDUL...
output:
417
result:
ok 1 number(s): "417"
Test #9:
score: 0
Accepted
time: 4ms
memory: 19084kb
input:
1 1000 1000 992010 LLLLLDLDRRLUDRR
output:
1999
result:
ok 1 number(s): "1999"
Test #10:
score: 0
Accepted
time: 4ms
memory: 19220kb
input:
1 1000 1000 919600 LLDLRUDRLURRUDRDRRDLRUDLRRRUUULDLDURDDDRUURRRLLURULDRLRLULLULDRULULRLRRRURLDDDRUUULUDLLLLRRLLRDDRDULUDLRLRLDRLUDUDURRULUULLDULUULDLLDRDULUDLDULDDUULDDRRURDRDULRRLDRRDUURURRLUUUDRRLDRRDDLULRDDLDLLRLRLLLRULUUUURRRLDLRUDRRLRURDRLDULLLUDRULLDLDRRUUDLRRLLRLDDLUDLRLRRURUUDUULUDURDURRLUU...
output:
944
result:
ok 1 number(s): "944"
Test #11:
score: 0
Accepted
time: 20ms
memory: 20116kb
input:
1 1000 1000 804351 DLRLDLLLLUDRDURRLDDRRLRUULURURDDDRDLRUDDULRRLLULURDRUUDRURRLURRRDRURRDRLULRDLRRDRRDDUDLUDLDULRUURRLRUUDRLDDRDDUUDULUULUUUDLRURULLRDUUDDDRRLDRUDDUUDRURLRDRUDLRLDDRRLLRLRDUDDULLULRLLDDUDDDUULDULLRRULULDUUULUDRRDRLUDLRRDDUDLRRDDLDLDRUULRRRRRLRLULLRDDRDDDULDRRURUDDLURLRLURLRDRULUDULUU...
output:
640000
result:
ok 1 number(s): "640000"