QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#503980 | #5414. Stop, Yesterday Please No More | vwxyz | TL | 15ms | 10636kb | Python3 | 2.6kb | 2024-08-04 03:37:06 | 2024-08-04 03:37:07 |
Judging History
answer
class Cumsum2:
def __init__(self,lst,mod=0):
self.H=len(lst)
self.W=len(lst[0]) if lst else 0
self.cumsum2=[[0]*(self.W+1) for i in range(self.H+1)]
for i in range(1,self.H+1):
for j in range(1,self.W+1):
self.cumsum2[i][j]=lst[i-1][j-1]
self.mod=mod
for i in range(self.H+1):
for j in range(1,self.W+1):
self.cumsum2[i][j]+=self.cumsum2[i][j-1]
if self.mod:
self.cumsum2[i][j]%=self.mod
for i in range(1,self.H+1):
for j in range(self.W+1):
self.cumsum2[i][j]+=self.cumsum2[i-1][j]
if self.mod:
self.cumsum2[i][j]%=self.mod
def __getitem__(self,tpl):
ab,cd=tpl
def make_slice(ij,N):
if type(ij)==int:
i,j=ij,ij+1
else:
i,j=ij.start,ij.stop
if i==None:
i=0
elif i<-N or N<i:
raise IndexError("list index out of range")
elif -N<=i<0:
i+=N
if j==None:
j=N
elif j<-N or N<j:
raise IndexError("list index out of range")
elif -N<=j<0:
j+=N
return i,j
a,b=make_slice(ab,self.H)
c,d=make_slice(cd,self.W)
retu=self.cumsum2[b][d]+self.cumsum2[a][c]-self.cumsum2[a][d]-self.cumsum2[b][c]
if self.mod:
retu%=self.mod
return retu
def __str__(self):
return str(self.cumsum2)
T=int(input())
for t in range(T):
N,M,K=map(int,input().split())
S=input()
le=len(S)
x0,x1=0,N
y0,y1=0,M
x,y=0,0
X,Y=[x],[y]
for s in S:
if s=="U":
x-=1
elif s=="D":
x+=1
elif s=="R":
y-=1
else:
y+=1
x0=max(x0,x)
x1=min(x1,N+x)
y0=max(y0,y)
y1=min(y1,M+y)
X.append(x)
Y.append(y)
x1=max(x1,x0)
y1=max(y1,y0)
minX=min(X)
minY=min(Y)
for i in range(le+1):
X[i]-=minX
Y[i]-=minY
leX=max(X)+1
leY=max(Y)+1
C=[[0]*leY for x in range(leX)]
for x,y in zip(X,Y):
C[x][y]=1
C=Cumsum2(C)
ans=0
for x in range(N):
for y in range(M):
dx,dy=x-X[0],y-Y[0]
if (x1-x0)*(y1-y0)==K+C[min(leX,max(0,x0-dx)):min(leX,x1-dx),min(leY,max(0,y0-dy)):min(leY,y1-dy)]:
ans+=1
print(ans)
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 15ms
memory: 10636kb
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
Time Limit Exceeded
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...