QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#503988 | #5414. Stop, Yesterday Please No More | vwxyz | TL | 870ms | 10896kb | Python3 | 1.2kb | 2024-08-04 03:40:27 | 2024-08-04 03:40:29 |
Judging History
answer
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+1) for x in range(leX+1)]
for x,y in zip(X,Y):
C[x+1][y+1]=1
for x in range(leX+1):
for y in range(1,leY+1):
C[x][y]+=C[x][y-1]
for x in range(1,leX+1):
for y in range(leY+1):
C[x][y]+=C[x-1][y]
def cumsum(a,b,c,d):
if a>=b or c>=d:
return 0
return C[b][d]+C[a][c]-C[a][d]-C[b][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+cumsum(max(0,x0-dx),min(leX,x1-dx),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: 7ms
memory: 10552kb
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: 528ms
memory: 10896kb
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: 859ms
memory: 10576kb
input:
1 1000 1000 979065 DDUULULUDULLULLDLUULURRLDURLRDLRRUURUUUDLRLUUDUUDUDLLDDDULU
output:
958416
result:
ok 1 number(s): "958416"
Test #4:
score: 0
Accepted
time: 870ms
memory: 10720kb
input:
1 1000 1000 943471 LRLDLURLDLRDRDUULULRDDLLRURDUURLLDDLDLDDLLLUUURLDRUDRLLUUUUUDLUUDLURURRDLRLRRRLULRRULURLRRDLDRLUDRRLDDLUDRRLLUDLLLRDULRRRRLDUUDRDLULUUUUDRRDULUDLLUUDLDURDRRLRRLDRLDDRURURLUULRRLDLLRLRDRRUULDLDLULLDLLRULLRUULURDURRLUUDUULLULDLRUDDLRLRLLUDDDLLLUDRRLDDULRRURRDURDDRDLLULRLULURLRDLLURD...
output:
889224
result:
ok 1 number(s): "889224"
Test #5:
score: -100
Time Limit Exceeded
input:
1 1000 1000 315808 LLRURURRDDDULLDDUDRDLRLLLDDDLUDRDURLDULRLRULUUDLUULUUDULLLLDDURLDUULUUDLLDLLDRUDUULRLLRLRUURLRLULLDDLLDUDLLRUUDRLDLUULDLLDRRRURDULLDRRRDURURDRLDURURUDLURLDURRLRRUDUDURDRLRRRDLRRURLURUDRRLDLRULLDLUURDURLURLLRDLRDRUURURDRUDUUUDLRRLUDLUUDUDDRRDUULUUDDRLLULDUUDRURRDRLULRLULDURLURUDLLD...