QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#705638 | #5414. Stop, Yesterday Please No More | Hanoist | RE | 1ms | 5728kb | C++14 | 2.2kb | 2024-11-03 00:14:28 | 2024-11-03 00:14:29 |
Judging History
answer
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<functional>
#include<utility>
#include<cassert>
using namespace std;
inline int read(){
int x = 0,f = 1;
char c = getchar();
while(c < '0' || c > '9'){
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9'){
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
return x * f;
}
const int N = 1e3 + 11;
int n,m,k;
char s[N * N];
int a[3 * N][3 * N],sum[3 * N][3 * N];
inline int calc(int x,int y,int xx,int yy){
return sum[xx][yy] - sum[x - 1][yy] - sum[xx][y - 1] + sum[x - 1][y - 1];
}
int main(){
int t,i,j,k,x,y,z;
t = read();
while(t--){
n = read(),m = read(),k = read();
scanf(" %s",s + 1);
int p = strlen(s + 1);
x = 0,y = 0;
int L = 0,R = 0,U = 0,D = 0;
for(i = 1;i <= p;i++){
if(s[i] == 'L') --x,L = min(L,x);
if(s[i] == 'R') ++x,R = max(R,x);
if(s[i] == 'U') --y,U = min(U,y);
if(s[i] == 'D') ++y,D = max(D,y);
L = -L,U = -U;
}
if(L + R >= m || U + D >= n){
if(!k) printf("%d\n",n * m);
else puts("0");
continue;
}
for(i = 1;i <= 3 * n;i++){
for(j = 1;j <= 3 * n;j++){
a[i][j] = 0;
}
}
int sx,sy;
sx = x = n,sy = y = m;
a[sx][sy] = 1;
for(i = 1;i <= p;i++){
if(s[i] == 'L') --y;
if(s[i] == 'R') ++y;
if(s[i] == 'U') --x;
if(s[i] == 'D') ++x;
a[x][y] = 1;
}
for(i = 1;i <= 3 * n;i++){
for(j = 1;j <= 3 * n;j++){
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
}
}
int res = 0;
for(i = sx;i > sx - n;i--){
for(j = sy;j > sy - m;j--){
int u = i + U,v = j + L;
if(calc(u,v,i + n - 1 - D,j + n - 1 - R) == k) ++res;
}
}
printf("%d\n",res);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5728kb
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
Runtime Error
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...